TY - GEN
T1 - Grid Embedding of 4-Connected plane graphs
AU - He, Xin
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W×H such that W+H≤n, W≤(n+3)/2 and H≤2(n−1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
AB - A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W×H such that W+H≤n, W≤(n+3)/2 and H≤2(n−1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
UR - https://www.scopus.com/pages/publications/84947915734
U2 - 10.1007/bfb0021812
DO - 10.1007/bfb0021812
M3 - Conference contribution
AN - SCOPUS:84947915734
SN - 3540607234
SN - 9783540607236
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 287
EP - 299
BT - Graph Drawing - Symposium on Graph Drawing, GD 1995, Proceedings
A2 - Brandenburg, Franz J.
PB - Springer Verlag
T2 - Symposium on Graph Drawing, GD 1995
Y2 - 20 September 1995 through 22 September 1995
ER -