Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area

verfasst von : Giuseppe Di Battista, Fabrizio Frati

Erschienen in: Thirty Essays on Geometric Graph Theory

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this chapter, we survey algorithms and bounds for constructing planar drawings of graphs in a small area.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Universal Sets for Straight-Line Embeddings of Bicolored Graphs
Nächstes Kapitel The Crossing-Angle Resolution in Graph Drawing
Literatur
1.
G.E. Andrews, A lower bound for the volumes of strictly convex bodies with many boundary points. Trans. Am. Math. Soc. 106, 270–279 (1963)MATHCrossRef
2.
P. Angelini, G. Di Battista, F. Frati, Succinct greedy drawings do not always exist, in Graph Drawing (GD’09), ed. by D. Eppstein, E.R. Gansner. LNCS, Springer, vol. 5849 (2010) pp. 171–182
3.
P. Angelini, T. Bruckdorfer, M. Chiesa, F. Frati, M. Kaufmann, C. Squarcella, On the area requirements of Euclidean minimum spanning trees (2011), manuscript
4.
P. Angelini, F. Frati, L. Grilli, An algorithm to construct greedy drawings of triangulations. J. Graph Algorithm. Appl. 14(1), 19–51 (2010)MathSciNetMATHCrossRef
5.
P. Angelini, F. Frati, M. Kaufmann, Straight-line rectangular drawings of clustered graphs. Discr. Comput. Geom. 45(1), 88–140 (2011)MathSciNetMATHCrossRef
6.
P. Angelini, F. Frati, M. Patrignani, Splitting clusters to get c-planarity, in Graph Drawing (GD’09), ed. by D. Eppstein, E.R. Gansner. LNCS, Springer, vol. 5849 (2010), pp. 57–68
7.
I. Bárány, J. Pach, On the number of convex lattice polygons. Comb. Prob. Comput. 1, 295–302 (1992)MATHCrossRef
8.
I. Bárány, G. Rote, Strictly convex drawings of planar graphs. Doc. Math. 11, 369–391 (2006)MathSciNetMATH
9.
10.
P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, I.G. Tollis, How to draw a series-parallel digraph. Int. J. Comput. Geom. Appl. 4(4), 385–402 (1994)MATHCrossRef
11.
P. Bertolazzi, G. Di Battista, G. Liotta, C. Mannino, Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)MathSciNetMATHCrossRef
12.
T.C. Biedl, Drawing outer-planar graphs in O(nlogn) area, in Graph Drawing (GD’02), ed. by M.T. Goodrich. LNCS, Springer, vol. 2528 (2002), pp. 54–65
13.
T.C. Biedl, Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discr. Comput. Geom. 45(1), 141–160 (2011)MathSciNetMATHCrossRef
14.
T.C. Biedl, F.J. Brandenburg, Drawing planar bipartite graphs with small area, in Canadian Conference on Computational Geometry (CCCG’05), University of Windsor, Ontario, Canada, 2005, pp. 105–108
15.
16.
T.C. Biedl, G. Kant, M. Kaufmann, On triangulating planar graphs under the four-connectivity constraint. Algorithmica 19(4), 427–446 (1997)MathSciNetMATHCrossRef
17.
18.
N. Bonichon, B. Le Saëc, M. Mosbah, Wagner’s theorem on realizers, in Automata, Languages and Programming (ICALP’02), ed. by P. Widmayer, F. Triguero Ruiz, R.M. Bueno, M. Hennessy, S. Eidenbenz, R. Conejo. LNCS, Springer, vol. 2380 (2002), pp. 1043–1053
19.
20.
F.J. Brandenburg, Drawing planar graphs on \(\frac{8} {9}{n}^{2}\) area. Electron. Notes Discr. Math. 31, 37–40 (2008)MathSciNetCrossRef
21.
A. Brocot, Calcul des rouages par approximation, nouvelle methode. Rev. Chronom. 6, 186–194 (1860)
22.
L. Cao, A. Strelzoff, J.Z. Sun, On succinctness of geometric greedy routing in Euclidean plane, in Pervasive Systems, Algorithms, and Networks (ISPAN’09), Kaohsiung, Taiwan, 2009, pp. 326–331
23.
T.M. Chan, M.T. Goodrich, S. Rao Kosaraju, R. Tamassia, Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom.: Theor. Appl. 23(2), 153–162 (2002)
24.
25.
C.C. Cheng, C.A. Duncan, M.T. Goodrich, S.G. Kobourov, Drawing planar graphs with circular arcs. Discr. Comput. Geom. 25(3), 405–418 (2001)MathSciNetMATHCrossRef
26.
N. Chiba, T. Yamanouchi, T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, ed. by J.A. Bondy, U.S.R. Murty (Academic Press, New York, 1984), pp. 153–173
27.
M. Chrobak, M.T. Goodrich, R. Tamassia, Convex drawings of graphs in two and three dimensions (preliminary version), in Symposium on Computational Geometry (SoCG’96), Philadelphia, Pennsylvania, USA, 1996, pp. 319–328
28.
M. Chrobak, G. Kant, Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geom. Appl. Limerick, Ireland, 7(3), 211–223 (1997)
29.
M. Chrobak, T.H. Payne, A linear-time algorithm for drawing a planar graph on a grid. Inform. Process. Lett. 54(4), 241–246 (1995)MathSciNetMATHCrossRef
30.
31.
P.F. Cortese, G. Di Battista, F. Frati, M. Patrignani, M. Pizzonia, C-planarity of c-connected clustered graphs. J. Graph Algorithm. Appl. Carleton University, Ottawa, Canada, 12(2), 225–262 (2008)
32.
P.F. Cortese, G. Di Battista, M. Patrignani, M. Pizzonia, Clustering cycles into cycles of clusters. J. Graph Algorithm. Appl. 9(3), 391–413 (2005)MATHCrossRef
33.
P.F. Cortese, G. Di Battista, M. Patrignani, M. Pizzonia, On embedding a cycle in a plane graph. Discr. Math. 309(7), 1856–1869 (2009)MATHCrossRef
34.
P. Crescenzi, G. Di Battista, A. Piperno, A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom.: Theor. Appl. 2, 187–200 (1992)
35.
E. Dahlhaus, A linear time algorithm to recognize clustered graphs and its parallelization, in Latin American Symposium on Theoretical Informatics (LATIN’98), ed. by C.L. Lucchesi, A.V. Moura. LNCS, Springer, vol. 1380 (1998), pp. 239–248
36.
H. de Fraysseix, J. Pach, R. Pollack, Small sets supporting Fáry embeddings of planar graphs, in Symposium on Theory of Computing (STOC’88), ed. by J. Simon, Chicago, Illinois, USA, (1988), pp. 426–433
37.
38.
39.
G. Di Battista, G. Drovandi, F. Frati, How to draw a clustered tree. J. Discr. Algorithm. 7(4), 479–499 (2009)MATHCrossRef
40.
G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Graph Drawing (Prentice Hall, Upper Saddle River, NJ, 1999)MATH
41.
G. Di Battista, F. Frati, Efficient c-planarity testing for embedded flat clustered graphs with small faces. J. Graph Algorithm. Appl. 13(3), 349–378 (2009)MATHCrossRef
42.
43.
G. Di Battista, W. Lenhart, G. Liotta, Proximity drawability: a survey, in Graph Drawing (GD’94), ed. by R. Tamassia, I.G. Tollis. LNCS, Princeton, New Jersey, USA, vol. 894 (1994), pp. 328–339
44.
G. Di Battista, G. Liotta, S. Whitesides, The strength of weak proximity. J. Discr. Algorithm. 4(3), 384–400 (2006)MATHCrossRef
45.
G. Di Battista, W.P. Liu, I. Rival, Bipartite graphs, upward drawings, and planarity. Inform. Process. Lett. 36(6), 317–322 (1990)MathSciNetMATHCrossRef
46.
G. Di Battista, R. Tamassia, Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175–198 (1988)MATHCrossRef
47.
48.
G. Di Battista, R. Tamassia, I.G. Tollis, Area requirement and symmetry display of planar upward drawings. Discr. Comput. Geom. 7, 381–401 (1992)MATHCrossRef
49.
G. Di Battista, R. Tamassia, L. Vismara, Incremental convex planarity testing. Inform. Comput. 169(1), 94–126 (2001)MATHCrossRef
50.
W. Didimo, F. Giordano, G. Liotta, Upward spirality and upward planarity testing, in Graph Drawing (GD’05), ed. by P. Healy, N. Nikolov. LNCS, vol. 3843 (2005), pp. 117–128
51.
52.
M.B. Dillencourt, W.D. Smith, Graph-theoretical conditions for inscribability and Delaunay realizability. Discr. Math. 161(1–3), 63–77 (1996)MathSciNetMATHCrossRef
53.
D. Dolev, H.W. Trickey, On linear area embedding of planar graphs. Technical report, Stanford University, Stanford, CA, 1981
54.
P. Eades, Q. Feng, X. Lin, H. Nagamochi, Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)MathSciNetMATHCrossRef
55.
P. Eades, Q. Feng, H. Nagamochi, Drawing clustered graphs on an orthogonal grid. J. Graph Algorithm. Appl. 3(4), 3–29 (1999)MathSciNetMATHCrossRef
56.
P. Eades, S. Whitesides, The logic engine and the realization problem for nearest neighbor graphs. Theor. Comput. Sci. 169(1), 23–37 (1996)MathSciNetMATHCrossRef
57.
P. Eades, S. Whitesides, The realization problem for Euclidean minimum spanning trees in NP-hard. Algorithmica 16(1), 60–82 (1996)MathSciNetMATHCrossRef
58.
D. Eppstein, M.T. Goodrich, Succinct greedy graph drawing in the hyperbolic plane, in Graph Drawing (GD’08), ed. by I.G. Tollis, M. Patrignani. LNCS, vol. 5417 (2009), pp. 14–25
59.
I. Fáry, On straight line representation of planar graphs. Acta Sci. Math. 11, 229–233 (1948)MATH
60.
S. Felsner, G. Liotta, S.K. Wismath, Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithm. Appl. 7(4), 363–398 (2003)MathSciNetMATHCrossRef
61.
Q. Feng, Algorithms for drawing clustered graphs. Ph.D. thesis, The University of Newcastle, Australia, 1997
62.
Q. Feng, R.F. Cohen, P. Eades, How to draw a planar clustered graph, in Computing and Combinatorics (COCOON’95), ed. by D. Du, M. Li. LNCS, Xi’an, China, vol. 959 (1995), pp. 21–30
63.
Q. Feng, R.F. Cohen, P. Eades, Planarity for clustered graphs, in European Symposium on Algorithms (ESA’95), ed. by P.G. Spirakis. LNCS, Corfu, Greece, vol. 979 (1995), pp. 213–226
64.
F. Frati, Straight-line drawings of outerplanar graphs in O(dnlogn) area, in Canadian Conference on Computational Geometry (CCCG’07), Carleton University, Ottawa, Canada 2007, pp. 225–228
65.
F. Frati, On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs. Int. J. Comput. Geom. Appl. 18(3), 251–271 (2008)MathSciNetMATHCrossRef
66.
F. Frati, Straight-line orthogonal drawings of binary and ternary trees, in Graph Drawing (GD’07), ed. by S.-H. Hong, T. Nishizeki, W. Quan. LNCS, Sydney, Australia, vol. 4875 (2008), pp. 76–87
67.
F. Frati, Lower bounds on the area requirements of series-parallel graphs. Discr. Math. Theor. Comput. Sci. 12(5), 139–174 (2010)MathSciNet
68.
F. Frati, M. Kaufmann, Polynomial area bounds for MST embeddings of trees. Tech. report RT-DIA-122-2008, Dept. of Computer Science and Automation, Roma Tre University, Rome, 2008
69.
F. Frati, M. Patrignani, A note on minimum area straight-line drawings of planar graphs, in Graph Drawing (GD’07), ed. by S.H. Hong, T. Nishizeki. LNCS, Sydney, Australia, vol. 4875 (2007), pp. 339–344
70.
A. Garg, M.T. Goodrich, R. Tamassia, Planar upward tree drawings with optimal area. Int. J. Comput. Geom. Appl. 6(3), 333–356 (1996)MathSciNetMATHCrossRef
71.
A. Garg, A. Rusu, Area-efficient order-preserving planar straight-line drawings of ordered trees. Int. J. Comput. Geom. Appl. 13(6), 487–505 (2003)MathSciNetMATHCrossRef
72.
A. Garg, A. Rusu, Straight-line drawings of general trees with linear area and arbitrary aspect ratio, in Computational Science and Its Applications (ICCSA’03), ed. by V. Kumar, M.L. Gavrilova, C.J.K. Tan, P. L’Ecuyer. LNCS, Montreal, Canada, vol. 2669 (2003), pp. 876–885
73.
A. Garg, A. Rusu, Straight-line drawings of binary trees with linear area and arbitrary aspect ratio. J. Graph Algorithm. Appl. Rome, Italy, 8(2), 135–160 (2004)
74.
A. Garg, A. Rusu, Area-efficient planar straight-line drawings of outerplanar graphs. Discr. Appl. Math. 155(9), 1116–1140 (2007)MathSciNetMATHCrossRef
75.
A. Garg, R. Tamassia, Efficient computation of planar straight-line upward drawings, in Graph Drawing (Proc. ALCOM Workshop on Graph Drawing), Sevres, Paris, 1994, pp. 298–306
76.
A. Garg, R. Tamassia, On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)MathSciNetMATHCrossRef
77.
M.T. Goodrich, G.S. Lueker, J.Z. Sun, C-planarity of extrovert clustered graphs, in Graph Drawing (GD’05), ed. by P. Healy, N. Nikolov. LNCS, Limerick, Ireland, vol. 3843 (2005), pp. 211–222
78.
M.T. Goodrich, D. Strash, Succinct greedy geometric routing in the Euclidean plane, in Algorithms and Computation (ISAAC’09), ed. by Y. Dong, D.-Z. Du, O.H. Ibarra. LNCS, Hawai, USA, vol. 5878 (2009), pp. 781–791
79.
M.T. Goodrich, C.G. Wagner, A framework for drawing planar graphs with curves and polylines. J. Algorithms 37(2), 399–421 (2000)MathSciNetMATHCrossRef
80.
C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, R. Weiskircher, Advances in c-planarity testing of clustered graphs, in Graph Drawing (GD’02), ed. by S.G. Kobourov, M.T. Goodrich. LNCS, Irvine, California, USA, vol. 2528 (2002), pp. 220–235
81.
C. Gutwenger, P. Mutzel, Planar polyline drawings with good angular resolution, in Graph Drawing (GD’98), ed. by S. Whitesides. LNCS, Montréal, Canada, vol. 1547 (1998), pp. 167–182
82.
X. He, Grid embedding of 4-connected plane graphs. Discr. Comput. Geom. 17(3), 339–358 (1997)MATHCrossRef
83.
X. He, H. Zhang, Succinct convex greedy drawing of 3-connected plane graphs, in Symposium on Discrete Algorithms (SODA’11), San Francisco, California, USA, 2011, pp. 1477–1486
84.
85.
V. Jelínek, E. Jelínková, J. Kratochvíl, B. Lidický, Clustered planarity: embedded clustered graphs with two-component clusters, in Graph Drawing (GD’08), ed. by I.G. Tollis, M. Patrignani. LNCS, Heraklion, Crete, Greece, vol. 5417 (2008), pp. 121–132
86.
V. Jelínek, O. Suchý, M. Tesař, T. Vyskočil, Clustered planarity: clusters with few outgoing edges, in Graph Drawing (GD’08), ed. by I.G. Tollis, M. Patrignani. LNCS, Heraklion, Crete, Greece, vol. 5417 (2008), pp. 102–113
87.
E. Jelínková, J. Kára, J. Kratochvíl, M. Pergel, O. Suchý, T. Vyskočil, Clustered planarity: small clusters in cycles and Eulerian graphs. J. Graph Algorithm Appl. 13(3), 379–422 (2009)MATHCrossRef
88.
89.
G. Kant, X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1–2), 175–193 (1997)MathSciNetMATHCrossRef
90.
M. Kaufmann, Polynomial area bounds for MST embeddings of trees, in Graph Drawing (GD’07), ed. by S.H. Hong, T. Nishizeki, W. Quan. LNCS, Sydney, Australia, vol. 4875 (2007), pp. 88–100
91.
M. Kaufmann, D. Wagner (eds.), Drawing Graphs, Methods and Models. Lecture Notes in Computer Science (Springer-Verlag, New York/Heidelberg, 2001)
92.
S.K. Kim, Simple algorithms for orthogonal upward drawings of binary and ternary trees, in Canadian Conference on Computational Geometry (CCCG’95), Quebec City, Quebec, Canada, 1995, pp. 115–120
93.
R. Kleinberg, Geographic routing using hyperbolic space, in IEEE Conference on Computer Communications (INFOCOM’07), Anchorage, Alaska, USA, 2007, pp. 1902–1909
94.
95.
W. Lenhart, G. Liotta, Proximity drawings of outerplanar graphs, in Graph Drawing (GD’96), ed. by S.C. North. LNCS, Berkeley, California, USA, vol. 1190 (1996), pp. 286–302
96.
G. Liotta, Computing proximity drawings of graphs. Ph.D. thesis, University of Rome “La Sapienza.” Rome, 1995
97.
G. Liotta, R. Tamassia, I.G. Tollis, P. Vocca, Area requirement of Gabriel drawings, in Algorithms and Complexity (CIAC’97), ed. by G.C. Bongiovanni, D.P. Bovet, G. Di Battista. LNCS, Rome, Italy, vol. 1203 (1997), pp. 135–146
98.
A. Lubiw, N. Sleumer, Maximal outerplanar graphs are relative neighborhood graphs, in Canadian Conference on Computational Geometry (CCCG’93), Waterloo, Ontario, Canada, 1993, pp. 198–203
99.
100.
D. Mondal, R.I. Nishat, Md. S. Rahman, Md. J. Alam, Minimum-area drawings of plane 3-trees, in Canadian Conference on Computational Geometry (CCCG’10), Manitoba, Canada, 2010, pp. 191–194
101.
102.
T. Nishizeki, N. Chiba, Planar Graphs: Theory and Algorithms (North Holland, Amsterdam, 1988)MATH
103.
104.
A. Papakostas, Upward planarity testing of outerplanar dags, in Graph Drawing, ed. by R. Tamassia, I.G. Tollis. LNCS, Springer, vol. 894 (1994), pp. 298–306
105.
P. Penna, P. Vocca, Proximity drawings in polynomial area and volume. Comput. Geom.: Theor. Appl. 29(2), 91–116 (2004)
106.
S. Rabinowitz, O(n 3) bounds for the area of a convex lattice n-gon. Geombinatorics 2, 85–88 (1993)MathSciNetMATH
107.
A. Rao, C.H. Papadimitriou, S. Shenker, I. Stoica, Geographic routing without location information, in ACM International Conference on Mobile Computing and Networking (MOBICOM’03), ed. by D.B. Johnson, A.D. Joseph, N.H. Vaidya, San Diego, California, USA, 2003, pp. 96–108
108.
R.C. Read, A new method for drawing a graph given the cyclic order of the edges at each vertex. Congressus Numerantium 56, 31–44 (1987)MathSciNet
109.
G. Rote, Strictly convex drawings of planar graphs, in Symposium on Discrete Algorithms (SODA’05), Vancouver, BC, Canada, 2005, pp. 728–734
110.
W. Schnyder, Embedding planar graphs on the grid, in Symposium on Discrete Algorithms (SODA’90), San Francisco, California, USA, 1990, pp. 138–148
111.
W. Schnyder, W. Trotter, Convex drawings of planar graphs. Abstr. Am. Math. Soc. 92T-05-135 (1992)
112.
C.S. Shin, S.K. Kim, K.Y. Chwa, Area-efficient algorithms for straight-line tree drawings. Comput. Geom.: Theor. Appl. 15(4), 175–202 (2000)
113.
S.K. Stein, Convex maps. Am. Math. Soc. 2, 464–466 (1951)MATH
114.
M.A. Stern, Ueber eine zahlentheoretische funktion. J. Reine Angew. Math. 55, 193–220 (1858)MATHCrossRef
115.
R. Tamassia (ed.), Handbook of Graph Drawing and Visualization (CRC Press), to appear
116.
R. Tamassia, I.G. Tollis, A unified approach to visibility representation of planar graphs. Discr. Comput. Geom. 1, 321–341 (1986)MathSciNetMATHCrossRef
117.
C. Thomassen, Planarity and duality of finite and infinite graphs. J. Comb. Theor. Ser. B 29(2), 244–271 (1980)MATHCrossRef
118.
C. Thomassen, Plane representations of graphs, in Progress in Graph Theory (Academic, 1984), pp. 43–69
119.
120.
121.
122.
K. Wagner, Bemerkungen zum vierfarbenproblem. Jahresbericht. German. Math.-Verein 2, 26–32 (1936)
123.
D. Woods, Drawing planar graphs. Ph.D. thesis, Stanford University, Stanford, CA, 1982
124.
125.
H. Zhang, S. Sadasivam, On planar polyline drawings, in Graph Drawing, ed. by S.-H. Hong, T. Nishizeki, W. Quan. LNCS, Springer, vol. 4875 (2008), pp. 213–218
126.
X. Zhou, T. Hikino, T. Nishizeki, Small grid drawings of planar graphs with balanced bipartition, in Algorithms and Computation (WALCOM’10), ed. by Md. S. Rahman, S. Fujita. LNCS, Dhaka, Bangladesh, vol. 5942 (2010), pp. 47–57
Metadaten
Titel
Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area
verfasst von
Giuseppe Di Battista
Fabrizio Frati
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Thirty Essays on Geometric Graph Theory

Print ISBN: 978-1-4614-0109-4

Electronic ISBN: 978-1-4614-0110-0

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-0110-0_9