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

Hanani–Tutte, Monotone Drawings, and Level-Planarity

verfasst von : Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič

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

A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Tóth showed that if a graph has an x-monotone drawing in which every pair of edges crosses an even number of times, then the graph has an x-monotone embedding in which the x-coordinates of all vertices are unchanged. We give a new proof of this result and strengthen it by showing that the conclusion remains true even if adjacent edges are allowed to cross each other oddly. This answers a question posed by Pach and Tóth. We show that a further strengthening to a “removing even crossings” lemma is impossible by separating monotone versions of the crossing and the odd crossing number.
Our results extend to level-planarity, which is a well-studied generalization of x-monotonicity. We obtain a new and simple algorithm to test level-planarity in quadratic time, and we show that x-monotonicity of edges in the definition of level-planarity can be relaxed.

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 Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs
Nächstes Kapitel On Disjoint Crossing Families in Geometric Graphs
Fußnoten
1
There is a gap in the original argument; an updated version is now available [24, 25].
 
2
On page 42 of [24], in the text after Lemma 2.1, D κ cannot necessarily be glued together without changing equivalence.
 
3
In this newer version, equivalence is redefined to mean having the same rotation system.
 
4
Walks are like paths except that vertices and edges can be repeated. In a closed walk, the last vertex is the same as the first vertex.
 
5
The examples in that paper allow multiple vertices in each layer, but these can be replaced by the requirement that vertices are not too close to edges to which they are not incident.
 
6
Tutte presented his theorem as an algebraic characterization of planarity, but he did not investigate algorithmic implications [31]. Algebraic planarity testing based on the Hanani–Tutte characterization was probably first described by Wu [33, 34] in a sequence of papers first published in Chinese in the 1970s.
 
7
There are linear-time algorithms for planarity testing based on a Hanani–Tutte-like characterization, but they do not take the algebraic route [4, 5].
 
8
The leveled graph
https://static-content.springer.com/image/chp%3A10.1007%2F978-1-4614-0110-0_14/MediaObjects/978-1-4614-0110-0_14_Figa_HTML.gif
  is such an example.
 
Literatur
1.
2.
3.
C. Chojnacki (Haim Hanani), Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fund. Math. 23, 135–142 (1934)
4.
H. de Fraysseix, Trémaux trees and planarity, in The International Conference on Topological and Geometric Graph Theory, Electronics Notes in Discrete Mathematics, vol. 31 (Elsevier Science B. V., Amsterdam, 2008), pp. 169–180
5.
H. de Fraysseix, P. Rosenstiehl, A characterization of planar graphs by Trémaux orders. Combinatorica 5(2), 127–135 (1985)MathSciNetMATHCrossRef
6.
G. Di Battista, E. Nardelli, Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybernet. 18(6), 1035–1046 (1988/1989)
7.
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
8.
A. Estrella-Balderrama, J. Joseph Fowler, S.G. Kobourov, On the characterization of level planar trees by minimal patterns, in Graph Drawing, ed. by D. Eppstein, E.R. Gansner. Lecture Notes in Computer Science, vol. 5849 (Springer-Verlag, Berlin, 2009), pp. 69–80
9.
10.
M. Harrigan, P. Healy, Practical level planarity testing and layout with embedding constraints, in Graph Drawing. Lecture Notes in Computer Science, vol. 4875 (Springer-Verlag, 2008), pp. 62–68
11.
P. Healy, A. Kuusik, Algorithms for multi-level graph planarity testing and layout. Theor. Comput. Sci. 320(2–3), 331–344 (2004)MathSciNetMATHCrossRef
12.
13.
L.S. Heath, S.V. Pemmaraju, Recognizing leveled-planar dags in linear time, in Graph Drawing, GD’95, ed. by F.J. Brandenburg. Lecture Notes in Computer Science, vol. 1027 (Springer-Verlag, Berlin, 1996), pp. 300–311
14.
L.S. Heath, S.V. Pemmaraju, Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput. 28(5), 1588–1626 (1999) (electronic)
15.
M. Jünger, S. Leipert, Level planar embedding in linear time. J. Graph Algorithm. Appl. 6(1), 67–113 (2002) (electronic)
16.
M. Jünger, S. Leipert, P. Mutzel, Level planarity testing in linear time, in Graph Drawing, Montréal, QC, 1998. Lecture Notes in Computer Science, vol. 1547 (Springer-Verlag, Berlin, 1998), pp. 224–237
17.
M. Jünger, S. Leipert, P. Mutzel, Pitfalls of using PQ-trees in automatic graph drawing, in Proceedings of the 5th International Symposium on Graph Drawing, GD’97, Rome, September 18–20, 1997, ed. by G. DiBattista. LNCS, vol. 1353 (Springer-Verlag, Berlin, 1998), pp. 193–204
18.
19.
S. Leipert, Level planarity testing and embedding in linear time. Ph.D. thesis, Universität zu Köln, Köln, 1998
20.
X. Lin, P. Eades, Towards area requirements for drawing hierarchically planar graphs. Theor. Comput. Sci. 292(3), 679–695 (2003)MathSciNetMATHCrossRef
21.
J. Matoušek, Using the Borsuk–Ulam theorem. Universitext (Springer, Berlin, 2003)
22.
J. Matousek, M. Tancer, U. Wagner, Hardness of embedding simplicial complexes in ℝ d , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, January 4–6, 2009, ed. by C. Mathieu (SIAM, Philadelphia, PA, 2009), pp. 855–864
23.
J. Pach, G. Tóth, Which crossing number is it anyway? J. Comb. Theor. Ser. B 80(2), 225–246 (2000)MATHCrossRef
24.
J. Pach, G. Tóth, Monotone drawings of planar graphs. J. Graph Theor. 46(1), 39–47 (2004)MATHCrossRef
25.
J. Pach, G. Tóth, Monotone drawings of planar graphs. ArXiv:1101.0967 e-prints (January 2011)
26.
J. Pach, G. Tóth, Monotone crossing number, in Proceedings of the 19th International Symposium on Graph Drawing, GD’11, Eindhoven, September 21–23, 2011, ed. by Marc J. Van Kreveld and Bettina Speckmann. LNCS, 7034 (Springer-Verlag, Berlin, 2012), pp. 278–289
27.
M.J. Pelsmajer, M. Schaefer, D. Štefankovič, Removing even crossings. J. Comb. Theor. Ser. B 97(4), 489–500 (2007)MATHCrossRef
28.
M.J. Pelsmajer, M. Schaefer, D. Štefankovič, Removing independently even crossings. SIAM J. Discr. Math. 24(2), 379–393 (2010)MATHCrossRef
29.
B. Randerath, E. Speckenmeyer, E. Boros, P.L. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs. Electron. Notes Discr. Math. 9, 269–277 (2001)CrossRef
30.
M. Schaefer, Hanani–Tutte and related results, in Geometry-Instuitive, Discrete and Convex-A Tribute to László Fejes Tóth (I.Bárány, K.J. Böröczky, G. Fejes Tóth, J. Pach, Eds.), Bolyai society Mathematical Studies, (Springer, Berlin) to apper
31.
32.
P. Valtr, On the pair-crossing number, in Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52 (Cambridge University Press, Cambridge, 2005), pp. 569–575
33.
W.J. Wu, On the planar imbedding of linear graphs. I. J. Syst. Sci. Math. Sci. 5(4), 290–302 (1985)MATH
34.
W.J. Wu, On the planar imbedding of linear graphs (continued). J. Syst. Sci. Math. Sci. 6(1), 23–35 (1986)MATH
Metadaten
Titel
Hanani–Tutte, Monotone Drawings, and Level-Planarity
verfasst von
Radoslav Fulek
Michael J. Pelsmajer
Marcus Schaefer
Daniel Štefankovič
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_14