Planar Graph, Via Schnyder’s Realizer, Ching-chi Lin, Hsueh-i Lu, I-fan Sun
Abstract. Let G be an n-node planar graph. In a visibility representation of G,eachnodeofG is represented by a horizontal line segment such that the line segments representing any two adjacent nodes...
Orderly Spanning Trees with Applications (2005)
Yi-ting Chiang, Ching-chi Lin, Hsueh-i Lu
Abstract. We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes canonical orderings, which exist only for triconnected plane graphs. Although not every...
Locally connected spanning trees on graphs (2004)
Lin, Ching-Chi, Chang, Gerard J., Chen, Gen-Huey
A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$. The purpose...
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer (2003)
Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun
Let G be an n-node planar graph. In a visibility representation of G, each node of G is represented by a horizontal segment such that the segments representing any two adjacent nodes of G are...
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer (2002)
Lin, Ching-Chi, Lu, Hsueh-I, Sun, I-Fan
Let $G$ be an $n$-node planar graph. In a visibility representation of $G$, each node of $G$ is represented by a horizontal line segment such that the line segments representing any two adjacent...
Orderly Spanning Trees with Applications (2001)
Chiang, Yi-Ting, Lin, Ching-Chi, Lu, Hsueh-I
We introduce and study the {\em orderly spanning trees} of plane graphs. This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs. Although not...
Orderly spanning trees with applications to graph encoding and graph drawing (2001)
Yi-ting Chiang, Ching-chi Lin, Hsueh-i Lu
The canonical ordering for triconnected planar graphs is a powerful method for designing graph algorithms. This paper introduces the orderly pair of connected planar graphs, which extends the concept...