Top

Published in:

2015 | OriginalPaper | Chapter

Small-Area Orthogonal Drawings of 3-Connected Graphs

Authors : Therese Biedl, Jens M. Schmidt

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most \(\frac{49}{64}n^2+O(n)\approx 0.76n^2\). In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to \(\frac{9}{16}n^2+O(n) \approx 0.56n^2\). The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Size- and Port-Aware Horizontal Node Coordinate Assignment

next chapter Simultaneous Embeddings with Few Bends and Crossings

The constructions we give have been designed as to keep the description simple; often even more grid-lines could be saved by doing more complicated constructions.

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)MATHMathSciNetCrossRef

Cheriyan, J., Maheshwari, S.N.: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms 9(4), 507–537 (1988)MATHMathSciNetCrossRef

Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comput. 34(4), 924–945 (2005)MATHMathSciNetCrossRef

de Fraysseix, H., de Mendez, P.O.: Regular orientations, arboricity and augmentation. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 111–118. Springer, Heidelberg (1995) CrossRef

Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: 19th Annual ACM Symposium on Theory of Computing, pp. 365–372 (1987)

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

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)MATHMathSciNetCrossRef

Mondshein, L.F.: Combinatorial ordering and the geometric embedding of graphs. Ph.D. thesis, M.I.T. Lincoln Laboratory / Harvard University (1971)

Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1–2), 83–110 (1998)MATHMathSciNetCrossRef

10.

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

11.

Schäffter, M.: Drawing graphs on rectangular grids. Discrete Appl. Math. 63, 75–89 (1995)MATHMathSciNetCrossRef

12.

Schmidt, J.M.: The Mondshein sequence (2013). http://arxiv.org/pdf/1311.0750.pdf

13.

Schmidt, J.M.: The Mondshein sequence. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 967–978. Springer, Heidelberg (2014)

14.

Biedl, T.: Optimal orthogonal drawings of triconnected plane graphs. In: McCune, W., Padmanabhan, R. (eds.) Automated Deduction in Equational Logic and Cubic Curves. LNCS, vol. 1095, pp. 333–344. Springer, Heidelberg (1996)

15.

Tamassia, R., Tollis, I.: A unified approach to visibility representations of planargraphs. Discrete Comput. Geom. 1, 321–341 (1986)MATHMathSciNetCrossRef

16.

Tamassia, R., Tollis, I.G., Vitter, J.S.: Lower bounds for planar orthogonal drawings of graphs. Inf. Process. Lett. 39, 35–40 (1991)MATHMathSciNetCrossRef

17.

Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. C–30(2), 135–140 (1981)MathSciNetCrossRef

Title: Small-Area Orthogonal Drawings of 3-Connected Graphs
Authors: Therese Biedl
Jens M. Schmidt
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-27261-0_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner