Selected Open Problems in Graph Drawing

Brandenburg, Franz J. and Eppstein, David and Goodrich, Michael T. and Kobourov, Stephen G. and Liotta, Giuseppe and Mutzel, Petra (2004) Selected Open Problems in Graph Drawing. In Liotta, Giuseppe, Eds. Proceedings Graph Drawing, pages pp. 515-539, Perugia.

Full text of this item is not available.

Abstract

In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.

Display Formats:	BibTex
EPrint Type:	Conference Paper
Subjects:	A General Literature > A.001 Introductory and Survey
ID Code:	489
Deposited By:	Selbach, Anna
Deposited On:	09 December 2004
Alternative Locations:	http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=515

References

J. Abello and K. Kumar. Visibility graphs and oriented matroids. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes in Comput. Sci., pages 147-158. Springer-Verlag, 1995.

O. Aichholzer, F. Aurenhammer, S.-W. Chen, N. Katoh, M. Taschwer, G. Rote, and Y.-F. Xu. Triangulations intersect nicely. Discrete Comput. Geom., 16:339-359, 1996.

O. Aichholzer, F. Aurenhammer, and H. Krasser. On the crossing number of complete graphs. In Proceedings of the 18th ACM Symposium on Computational Geometry, pages 19-24. ACM Press, 2002.

B. Aronov, P. Erdös, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, and L. J. Schulman. Crossing families. Combinatorica, 14:127-134, 1994.

W. Barth, M. Jünger, and P. Mutzel. Simple and efficient cross counting. In M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD'02), volume 2528 of Lecture Notes in Comput. Sci., pages 130-141. Springer-Verlag, 2002.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In WADS '97, volume 1272 of Lecture Notes in Comput. Sci., pages 331-334, 1998.

S. Bhatt and S. Cosmadakis. The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett., 25:263-267, 1987.

S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci., 28:300-343, 1984.

T. Biedl. Drawing outer-planar graphs in 0(n log n) area. In M. Goodrich, editor, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Comput. Sci., pages 54-65. Springer-Verlga, 2002.

D. Bienstock and N. Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17:333, 1993.

R. Blankenship and B. Oporowski. Book embeddings of graphs and minor-closed classes. In Thirty-Second Southeastern Internat. Conf. Combinatorics, Graph Theory and Computing, page 30, Baton Rouge, Dept. of Mathematics, Louisiana State University, 2001. http//www.math.lsu.edu/~conf_se/program.pdf.

P. Bose. On embedding an outer-planar graph in a point set. Comput. Geom., 23(3):303-312, 2002.

P. Bose, W. Lenhart, and G. Liotta. Characterizing proximity trees. Algorithmica, 16:83-110, 1996.

G. Cairns and Y. Nikolayevsky. Bounds for generalized thrackles. Discrete Comput. Geom., 23(2):191-206, 2000.

T. Calamoneri and A. Sterbini. 3D straight-line grid drawing of 4-colorable graph. Inform. Process. Lett., 63(2):97-102, 1997.

G. Calinescu, C. G. Fernandes, U. Finkler, and H. Karloff. A better approximation algorithm for finding planar subgraphs. In Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 16-25, 1996.

T. Chan. A near-linear area bound for drawing binary trees. Algorithmica, 34:1-13, 2001.

T.M. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia. Optimizing area and aspect ratio in straight-line orthogonal tree drawings. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes in Comput. Sci., pages 63-75. Springer-Verlag, 1997.

B. Chazelle. Reporting and counting segment intersections. J. Comput. Syst. Sci., 32:156-182, 1986.

B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6:485-524, 1991.

B. Chazelle and J. Incerpi. Triangulation and shape-complexity. ACM Trans. Graph., 3(2):135-152, 1984.

S.-W. Cheng and Y.-F. Xu. On \beta-skeleton as a subgraph of the minimum weight triangulation. Theoretical Computer Science, 262(1-2):459-471, 2001.

M. Chrobak, M. T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319-328, 1996.

M. Chrobak and S. ichi Nakano. Minimum-width grid drawings of plane graphs. Comput. Geom. Theory Appl., 11:29-54, 1998.

M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. Internat. J. Comput. Geom. Appl., 7(3):211-223, 1997.

M. Chrobak and H. Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20, 1989.

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17:199-208, 1997.

E. Dahlhaus. Linear time algorithm to recognize clustered planar graphs and its parallelization. In C. Lucchesi, editor, 3rd Latin American Symposium on Theoretical Informatics (LATIN ')(), volume 1380 of Lecture Notes Comput. Sci., pages 239-248. Springer-Verlag, 1998.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

O. Devillers, G. Liotta, F. P. Preparata, and R. Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. Theory Appl., 11:187-208, 1998.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303-325, 1997.

G. Di Battista and G. Liotta. Upward planarity checking: "Faces are more than polygons". In S. Whitesides, editor, Graph Drawing (Proc. GD '98), Lecture Notes in Comput. Sci., pages 72-86. Springer-Verlag, 1998.

G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Orthogonal drawings of cycles in 3D space. In J. Marks, editor, Graph Drawing (Proc. GD '00), Lecture Notes in Comput. Sci. Springer-Verlag 2000.

G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Embedding problems for paths with direction constrained edges. Theoretical Computer Science, 289(2):897, 2002.

G. Di Battista, G. Liotta, and F. Vargiu. Sprality and optimal orthogonal drawings. SIAM J. Comput., 27(6):1764-1811, 1998.

G. Di Battista and L. Vismara. Angles of planar triangular graphs. SIAM J. Discrete Math., 9(3):349-359, 1996.

E. Di Giacomo. Drawing series-parallel graphs on restricted integer 3D grids. In Graph Drawing (Proc. GD 03), Lectue Notes in Comput. Sci., 2003. These proceedings.

E. Di Giacomo, G. Liotta, and H. Meijer. 3D straight-line drawings of k-trees. Technical Report TR-2003-473, Queen's University, School of Computing, 2003.

E. Di Giacomo, G. Liotta, and M. Padrignani. Orthogonal 3D shapes of theta graphs. In M. Goodrich, editor, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Comput Sci., pages 142-149. Springer-Verlag, 2002.

E. Di Giacomo, G. Liotta, and S. Wismath. Drawing series-parallel graphs on a box. In 14th Canadian Conference On Computational Geometry (CCCG '02), 2002.

E. Di Giacomo and H. Meijer. Track drawings of graphs with constant queue number. These proceedings, 2003.

M. Dickerson, J. Keil, and M. Montague. A large subgraph of the minimum weight triangulation. Discrete and Computational Geometry, 18:289-304, 1997.

M. T. Dickerson and M. H. Montague. A (usually?) connected subgraph of the minimum weight triangulation. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 204-213, 1996.

H. Dijdjev and I. Vrto. An improved lower bound for crossing numbers. In M. Jünger, S. Leipert, and P. Mutzel, editors, Graph Drawing (Proc. GD '01), Lecture Notes in Comput. Sci. Springer-Verlag, 2001. to appear.

M. B. Dillencourt. Realizability of Delaunay triangulations. Inform. Process. Lett., 33(6):283-287, Feb. 1990.

M. B. Dillencourt, D. Eppstein, and D. S. Hirschberg. Geometric thickness of complete graphs. J. Graph Algorithms & Applications, 4(3):5-17, 2000.

M. B. Dillencourt and W. D. Smith. Graph-theoretical conditions for inscribabiliy and Delaunay realizability. In Proc. 6th Canad. Conf. Comput. Geom., pages 287-292, 1994.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. Mc Cartin, N. Nishimura, P. Radge, F. Rosamond, M. Suderman, S. Whitesides, and D. Wood. On the parameterized complexity of layered graph drawing. In F. M. auf der Heide, editor, Algorithms, 9th European Symposium (ESA '01), volume 2161 of Lecture Notes in Comput. Sci., pages 488-499. Springer-Verlag, 2001.

V. Dujmovic, P. Morin, and D. Wood. Pathwidth and three-dimensional straight line grid drawings of graphs. In M. T. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Comput. Sci., pages 42-53. Springer-Verlag, 2002.

V. Dujmovic and D. R. Wood. Tree partitions of K-trees with applications in graph layout. Technical Report 02-03, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada, 2002.

V. Dujmovic and D. R. Wood. On linear layouts of graphs. Technical Report 03-05, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada, 2003.

V. Dujmovic and D. R. Wood. Stacks, queues and tracks: Layouts of graphs subdivisions. Technical Report 03-07, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada, 2003.

V. Dujmovic and D. R. Wood. Three-dimensional grid drawings with subquadratic volume. In Graph Drawing (Proc. GD 03), Lecture Notes in Comput. Sci., 2003. These proceedings.

V. Dujmovic and D. R. Wood. Track layouts of graphs. Technical Report 03-06, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada, 2003.

V. Dujmovic and D. R. Wood. Tree-partitions of k-trees with application in graph layout. In Workshop on Graph Theoretic Concepts in Computer Science (Proc. WG '03), Lecture Notes in Comput. Sci. Springer-Verlag, to appear.

P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees in NP-hard. Algorizhmica, 16:60-82, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

B. Edler. Effiziente Algorithmen für flächenminimale Layouts von Bäumen. Diplomarbeit, Universität Passau, 1999.

H. ElGindy, D. Avis, and G. T. Toussaint. Applications of a two-dimensional hidden-line algorithm to other geometric problems. Computing, 31:191-202, 1983.

G. Even, S. Guha, and B. Schieber. Improved approximations of crossings in graph drawing and VLSI layout area. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'00), pages 296-305. ACM Press, 2000.

H. Everett. Visibility graph recognition. Report 231/90, Dept. Comput. Sci., Univ. Toronto, Toronto, ON, 1990. Ph.D. Thesis.

S. Felsner. Convex drawings of planar graphs and the order dimenssion of 3-polytopes. Order, 18(1):19-37, 2001.

S. Felsner, G. Liotta, and S. Wismath. Straight line drawings on restricted integer grids in two and three dimensions. In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph DRawing (Proc. GD '01), volume 2265 of Lecture Notes in Comput. Sci., pages 328-342. Springer-Verlag, 2001.

Q.-W. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In P. G. Spirakis, editor, Algorithms - ESA '95, Third Annual European Symposium, volume 979 of Lecture Notes in Computer Science, pages 213-226, Corfu, Greece, 25-27 Sept. 1995. Springer.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.

M. R. Garey and D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Inform. Process. Lett., 7:175-179, 1978.

A. Garg. New results on drawing angle graphs. Comput. Geom. Theory Appl., 9(1-2):43-82, 1998.

A. Garg, M. T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. Internat. J. Comput. Geom. Appl., 6:333-356, 1996.

A. Garg and G. Liotta. Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time. In J. Kratochvil, editor, Graph Drawing (Proc. GD '99), Lecture Notes in Comput. Sci. Springer-Verlag, 1999.

A. Garg and A. Rusu. Straight-line drawings of binary trees with linear area and good aspect ratio. In M. Goodrich, editor, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes Comput. Sci., pages 320-331. Springer-Verlga, 2002.

A. Garg and A. Rusu. Area-efficient drawings of outerplanar graphs. In Graph Drawing (Proc.GD 03), Lecture Notes in Comput. Sci., 2003. These proceedings.

A. Garg and R. Tamassia. A new minimum cost flow algorithm with applications to graph drawing. In S. C. North, editor, Graph Drawing (Proc. GD '96), Lecture Notes Comput. Sci. Springer-Verlag, 1997.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601-625, 2001.

A. Garg, R. Tamassia, and P. Vocca. Drawing with colors. In Proc. 4th Annu. European Sympos. Algorithms, volume 1136 of Lecture Notes Comput. Sci., pages 12-26. Springer-Verlag, 1996.

S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete Comput. Geom., 17:143-162, 1997.

A. Gregori. Unit length embedding of binary trees on a square grid. Inform. Process. Lett., 31:167-172, 1989.

M. Grohe. Computing crossing numbers in quadraic time. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'00), pages 231-236. ACM Press, 2000.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Advances in c-planarity testing of clustered graphs. In M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD'02), volume 2528 of Lecture Notes in Comput. Sci., pages 220-325. Springer-Verlag, 2002.

C. Gutwenger and P. Mutzel. An experimental study of crossing minimization heuristics. In Graph Drawing (Proc. GD'03), Lecture Notes in Comput. Sci., 2003. These proceedings.

C. Gutwenger and P. Mutzel. Graph embedding with minimum depth and maximum external face. In Graph Drawing (Proc. GD'03), Lecture Notes in Comput. Sci., 2003. These proceedings.

C.Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. In Proc. Ninth Annual ACM-SIAM Symp. Discrete Algorithms (SODA '2001), pages 246-255, Washington, DC, 2001. ACM Press.

P. Healy and A. Kuusik. The vertex-exchange graph: a new concept for multi-level crossing minimization. In J. Kratochvíl, editor, Graph Drawing (Proc. GD '99), volume 1731 of Lecture Notes in Comput. Sci., pages 205-216. Springer-Verlag, 1999.

S. Hertel and K. Mehlhorn. Fast triangulation of the plane with respect to simple polygons. Inform. Control, 64:52-76, 1985.

J. W. Jaromczyk and G. T. Toussaint. Relative neighborhood graphs and their relatives. Proc. IEEE, 80(9):1502-1517, Sept. 1992.

M. Jünger, E. Lee, P. Mutzel, and T. Odenthal. A polyhedral approach to the multi-layer crossing number problem. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes in Comput. Sci., pages 13-24. Springer-Verlag, 1997.

G. Kant. A new method for planar graph drawings on a grid. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 101-110, 1992.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

M. Keil. Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl., 4:13-26, 1994.

D. G. Kirkpatrick. A note on Delaunay and optimal triangulations. Inform. Process. Lett., 10(3):127-128, 1980.

G. W. Klau, K. Klein, and P. Mutzel. An experimental comparison of orthogonal compaction algorithms. In Graph Drawing )Proc. GD 2000), Lecture Notes Comput. Sci. Springer Verlag, 2001.

G. W. Klau and P. Mutzel. Optimal compaction of orthogonal grid drawings. In and Combinatorial Optimization, volume 1610 of Lecture Notes Comput. Sci., pages 304-319. Springer-Verlag, 1999.

F. T. Leighton. New lower bound techniques for VLSI. In Proc. 22nd Annu. IEEE Sympos. Found. Comput. Sci., pages 1-12, 1981.

F. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, 1999.

W. Lenhart and G. Liotta. Drawing outerplanar minimum weight triangulations. Inform. Process. Lett., 57(5):253-260, 1996.

W. Lenhart and G. Liotta. Proximity drawings of outerplanar graphs. In Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci. Springer-Verlag, 1997.

W. Lenhart and G. Liotta. The drawability problem for minimum weight triangulations. Theoret. Comp. Sci., 270:261-286, 2002.

C. Levcopoulos and D. Krznaric. Tight lower bounds for minimum weight triangulation heuristic. Inform. Process. Lett., 57:129-135, 1996.

C. Levcopoulos and D. Krznaric. A linear-time approximation schema for minimum weight triangulation of convex polygons. Algorithmica, 21:285-311, 1998.

A. Lingas. A new heuristic for minimum weight triangulation. SIAM J. Algebraic Discrete Methods, 8(4):646-658, 1987.

G. Liotta and G. Di Battista. Computing proximity drawings of trees in the 3-dimensional space. In Proc. 4th Workshop Algorithms Data Struct., volume 955 of Lecture Notes Comput. Sci., pages 239-250. Springer-Verlag, 1995.

G. Liotta, A. Lubiw, H. Meijer, and S. H. Whitesides. The rectangle of influence drawability problem. Comput. Geom. Theory Appl., 10(1):1-22, 1998.

G. Liotta and H. Meijer. Voronoi drawings of trees. Comput. Geom. Theory Appl., 2003. to appear.

L. Lovasz, K. Vesztergombi, U. Wagner, and E. Welzl. Convex quadrilaterals and k-sets. Contemporary Mathematics, 2003.

A. Lubiw and N. Sleumer. Maximal outerplanar graphs are relative neighborhood graphs. In Proc. 5th Canad. Conf. Geom., pages 198-203, 1993.

S. Malitz and A. Papakostas. On the angular resolution of planar graphs. In Proc. 24th Annu. ACM Sympos. Theory Comput., pages 527-538, 1992.

G. K. Manacher and A. L. Zobrist. Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inform. Process. Lett., 9:31-34, 1979.

A. Mansfield. Determining the thickness of a graph is NP-hard. Math. Proc. Cambridge Philos. Soc., 93(9):9-23, 1983.

K. Mehlhorn, T. S. S. Näher, S. Schirra, M. Seel, R. Seidel, and C. Uhrig. Checking geometric structures. Comput. Geom. Theory Appl., 12:85-113, 1999.

C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Discrete Comput. Geom., 8:265-293, 1992.

P. Mutzel and R. Weiskircher. Computing optimal embeddings for planar graphs. In D.-Z. Du, P. Eades, V. Estivill-Castro, X. Lin, and A. Sharma, editors, Computing and Combinatorics, Proc. Sixth Annual Internat. Conf. (COCOON'2000), volume 1858 of Lecture Notes in Comput. Sci., pages 95-104. Springer-Verlag, 2000.

J. Pach, F. Shahrokhi, and M. Szegedy. Applications of the crossing number. Algorithmica, 16:111-117, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

J. Pach, T. Thiele, and G. Tóth. Three-dimensional grid drawings of graphs. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 47-51. Springer-Verlag, 1997.

J. Pach and G. Tóth. Graphs drawn with few crossings per edge. Combinatorica, 17:427-439, 1997.

M. Pizzonia and R. Tamassia. Minimum depth graph embedding. In Proc. European Symposium on Algorithms (ESA 2000), Lecture Notes in Comput Science. Springer-Verlag, 2000.

E. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, Oct. 1990.

S. Rahman, N. Egi, and T. Nishizeki. No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. In Graph Drawing (Proc. GD 03), Lecture Notes in Comput. Sci., 2003. These proceedings.

D. Rappaport and H. Meijer. Computing the minimum weight triangulation of a set of linearly ordered points. Information Processing Letters, 42:35-38, 1992.

R. Richter and C. Thomassen. Relations between crossing numbers of complete and complete bipartite graphs, February 1997.

P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom., 1(4):343-353, 1986.

E. R. Scheinerman and H. S. Wilf. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability. Amer. Math. Monthly, 101(10):939-943, 1994.

W. Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.

W. Schnyder and W. T. Trotter. Convex embeddings of 3-connected plane graphs. Abstracts of the AMS, 13(5):502, 1992.

C.-S. Shin, S. K. Kim, and K.-Y. Chwa. Area-efficient algorithms for straight-line tree drawings. Comput. Geom. Theory Appl., 15:175-202, 2000.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern., SMC-11(2):109-125, 1981.

O. Sykora and I. Vrto. On VLSI layouts of the star graph and related networks. The VLSI Journal, 17:83-93, 1994.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

G. Toussaint. Efficient triangulation of simple polygons. Visual Comput., 7:280-295, 1991.

G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355-372, 1985.

V. Vijayan. Geometry of planar graphs with angles. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pages 116-124, 1986.

V. Waddle and A. Malhotra. An E log E line crossing algorithm for levelled graphs. In J. Kratochvil, editor, Graph Drawing (Proc. GD '99), Lecture Notes Comput. Sci., pages 59-70. Springer-Verlag, 1999.

C. A. Wang, F. Y. Chin, and Complexity (Proc. CIAC 2000), volume 1767 of Lecture Notes Comput. Sci., pages 163-173. Springer-Verlag, 2000.

T. C. Woo and S. Y. Shin. A linear time algorithm for triangulating a point-visible polygon. ACM Trans. Graph., 4(1):60-70, 1985.

D. R. Wood. Queue layouts, tree-width, and three-dimensional graph drawing. In 22nd Foundations of Software Technology and Theoretical Comput. Sci. (FSTTCS '02), volume 2556 of Lecture Notes in Comput. Sci., pages 348-359, 2002.

H. Zhang and X. He. Compact visibility representations and straight-line grid embedding of plane graphs. In Proc. 8th International Workshop on Algorithms and Data Structures (WADS '03), volume 2748 of LNCS, pages 493-504. Springer, 2003.