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

Rectangle and Square Representations of Planar Graphs

verfasst von : Stefan Felsner

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 the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular drawings, the corners of the rectangles represent the vertices. The graph obtained by taking the rectangles as vertices and contacts as edges is the rectangular dual. In visibility graphs and segment contact graphs, the vertices correspond to horizontal or to horizontal and vertical segments of the dissection. Special orientations of graphs turn out to be helpful when dealing with characterization and representation questions. Therefore, we look at orientations with prescribed degrees, bipolar orientations, separating decompositions, and transversal structures.
In the second part, we ask for representations by a dissections of a rectangle into squares. We review results by Brooks et al. [The dissection of rectangles into squares. Duke Math J 7:312–340 (1940)], Kenyon [Tilings and discrete Dirichlet problems. Isr J Math 105:61–84 (1998)], and Schramm [Square tilings with prescribed combinatorics. Isr J Math 84:97–118 (1993)] and discuss a technique of computing squarings via solutions of systems of linear equations.
Mathematics Subject Classification (2010): 05C10, 05C62, 52C15.

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 Mover Problems
Nächstes Kapitel Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs
Literatur
1.
M.J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S.G. Kobourov, T. Ueckerdt, Computing cartograms with optimal complexity. In Proceedings of the 2012 symposuim on Computational Geometry (SoCG’12). ACM, Chapel Hill, North Carolina, USA, pp. 21–30 (2012)
2.
A.L. Buchsbaum, E.R. Gansner, C.M. Procopiuc, S. Venkatasubramanian, Rectangular layouts and contact graphs. ACM Trans. Algorithms 4(1), 8–28 (2008)MathSciNetCrossRef
3.
4.
B. Bollobas, Modern Graph Theory (Springer-Verlag, New york, 2002)
5.
J. Bhasker, S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica 3, 247–278 (1988)MathSciNetMATHCrossRef
6.
7.
R.L. Brooks, C.A.B. Smith, A.H. Stone, W.T. Tutte, The dissection of rectangles into squares. Duke Math. J. 7, 312–340 (1940)MathSciNetCrossRef
8.
J. Chalopin, D. Gonçalves, Every planar graph is the intersection graph of segments in the plane, in Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), Bethesda, Maryland, USA, pp. 631–638 (2009)
9.
10.
G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Graph Drawing (Prentice Hall, Englewood Cliffs, NJ, 1999)MATH
11.
H. de Fraysseix, P. Ossona de Mendez, On topological aspects of orientation. Discr. Math. 229, 57–72 (2001)MATHCrossRef
12.
H. de Fraysseix, P. Ossona de Mendez, J. Pach, A left-first search algorithm for planar graphs. Discr. Comput. Geom. 13, 459–468 (1995)MATHCrossRef
13.
H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, Bipolar orientations revisited. Discr. Appl. Math. 56, 157–179 (1995)MATHCrossRef
14.
15.
M. Eiglsperger, S. Fekete, G.W. Klau, Orthogonal graph drawing, in Drawing Graphs: Methods and Models. LNCS, vol. 2025 (Tutorial) (Springer-Verlag, 2001), pp. 121–171
16.
D. Eppstein, E. Mumford, B. Speckmann, K. Verbeek, Area-universal rectangular layouts, in Proceedings of the 25th Symposium on Computational Geometry, Aarhus, Denmark, pp. 267–276 (2009)
17.
S. Felsner, Geometric Graphs and Arrangements. Advanced Lectures in Mathematics (Vieweg Verlag Wiesbaden, 2004)
18.
S. Felsner, Lattice structures from planar graphs. Electr. J. Comb. 11(R15), 24 pp. (2004)
19.
S. Felsner, É. Fusy, M. Noy, D. Orden, Bijections for Baxter families and related objects. J. Comb. Theor. A 18, 993–1020 (2011)MathSciNetCrossRef
20.
S. Felsner, C. Huemer, S. Kappes, D. Orden, Binary labelings for plane quadrangulations and their relatives. Discr. Math. Theor. Comput. Sci. 12(3), 115–138 (2010)MathSciNet
21.
J.-H. Fan, C.-C. Lin, H.-I. Lu, H.-C. Yen, Width-optimal visibility representations of plane graphs, in Proceedings of the 18th International Conference on Algebraic and Computation (ISAAC). LNCS, vol. 4835 (Springer, 2007), pp. 160–171
22.
23.
E. Fusy, Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discr. Math. 309(7), 1870–1894 (2009)MathSciNetMATHCrossRef
24.
J. Graver, B. Servatius, H. Servatius, Combinatorial Rigidity. Grad. Stud. in Math., vol. 2 (American Math. Soc., Providence, RI, 1993)
25.
26.
P. Hliněný, Contact graphs of line segments are NP-complete. Discr. Math. 235, 95–106 (2001)MATHCrossRef
27.
28.
R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, D. Souvaine, I. Streinu, W. Whiteley, Planar minimally rigid graphs and pseudo-triangulations. Comput. Geom. 31, 31–61 (2005)MathSciNetMATHCrossRef
29.
30.
31.
G. Kant, X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172, 175–193 (1997)MathSciNetMATHCrossRef
32.
G. Kirchhoff, Über die Auflösung der lichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72, 497–508 (1847)
33.
34.
J. Kratochvíl, A. Kuběna, On intersection representations of co-planar graphs. Discr. Math. 178, 251–255 (1998)MATHCrossRef
35.
P. Koebe, Kontaktprobleme der konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88, 141–164 (1936)
36.
37.
38.
39.
40.
K. Miura, H. Haga, T. Nishizeki, Inner rectangular drawings of plane graphs. Int. J. Comput. Geom. Appl. 16(2–3), 249–270 (2006) [in English]
41.
42.
S. Mozes, C. Wulff-Nilsen, Shortest paths in planar graphs with real lengths in \(\mathcal{O}({n\log }^{2}n/\log \log n)\) time, in ESA 2010. LNCS, vol. 6347 (Springer, 2010), pp. 206–217
43.
T. Nishiseki, M.S. Rhaman, Planar Graph Drawing (World Scientific, Singapore, 2004)
44.
45.
M. Rahman, S.-i. Nakano, T. Nishizeki, Box-rectangular drawings of plane graphs. J. Algorithms 37(2), 363–398 (2000)
46.
P. Rosenstiehl, Embedding in the plane with orientation constraints: the angle graph. Ann. NY Acad. Sci. 555, 340–346 (1989)MathSciNetCrossRef
47.
P. Rosenstiehl, R.E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discr. Comput. Geom. 1, 343–353 (1986)MathSciNetMATHCrossRef
48.
49.
50.
J. Skinner, C. Smith, W. Tutte, On the dissection of rectangles into right-angled isosceles triangles, J. Comb. Theor. Ser. B 80, 277–319 (2000)MathSciNetMATHCrossRef
51.
K. Stephenson, Introduction to Circle Packing: The Theory of Discrete Analytic Functions (Cambridge University Press, Cambridge, 2005)
52.
53.
54.
C. Thomassen, Plane representations of graphs, in Progress in Graph Theory, ed. by Bondy, Murty (Academic Press, 1984), pp. 336–342
55.
R. Tamassia, I.G. Tollis, A unified approach to visibility representations of planar graphs. Discr. Comput. Geom. 1, 321–341 (1986)MathSciNetMATHCrossRef
56.
57.
58.
T. Ueckerdt, Geometric representations of graphs with low polygonal complexity. Ph.D. thesis, Technische Universität Berlin, 2011
59.
60.
H. Zhang, X. He, Visibility representation of plane graphs via canonical ordering tree. Inform. Process. Lett. 96, 41–48 (2005)MathSciNetMATHCrossRef
Metadaten
Titel
Rectangle and Square Representations of Planar Graphs
verfasst von
Stefan Felsner
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_12