Skip to main content

2016 | OriginalPaper | Buchkapitel

Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time

verfasst von : Seok-Hee Hong, Hiroshi Nagamochi

Erschienen in: Graph Drawing and Network Visualization

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335–341, 1988].
In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293–1320 (2016)MathSciNetCrossRefMATH Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293–1320 (2016)MathSciNetCrossRefMATH
3.
Zurück zum Zitat Eades, P., Hong, S.-H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65–76 (2013)MathSciNetCrossRefMATH Eades, P., Hong, S.-H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65–76 (2013)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Fáry, I.: On straight line representations of planar Graphs. Acta Sci. Math. Szeged 11, 229–233 (1948)MATH Fáry, I.: On straight line representations of planar Graphs. Acta Sci. Math. Szeged 11, 229–233 (1948)MATH
6.
Zurück zum Zitat Grigoriev, A., Bodlaender, H.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)MathSciNetCrossRefMATH Grigoriev, A., Bodlaender, H.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)MathSciNetCrossRefMATH
7.
Zurück zum Zitat Hong, S.-H., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 72(4), 1033–1054 (2015)MathSciNetCrossRefMATH Hong, S.-H., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 72(4), 1033–1054 (2015)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: Fáry’s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 335–346. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32241-9_29 CrossRef Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: Fáry’s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 335–346. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32241-9_​29 CrossRef
9.
Zurück zum Zitat Hong, S.-H., Nagamochi, H.: Re-embedding a 1-plane graph into a straight-line drawing in linear time. Technical report TR 2016–002, Department of Applied Mathematics and Physics, Kyoto University (2016) Hong, S.-H., Nagamochi, H.: Re-embedding a 1-plane graph into a straight-line drawing in linear time. Technical report TR 2016–002, Department of Applied Mathematics and Physics, Kyoto University (2016)
11.
Zurück zum Zitat Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and Hardness of 1-planarity testing. J. Graph Theory 72(1), 30–71 (2013)MathSciNetCrossRefMATH Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and Hardness of 1-planarity testing. J. Graph Theory 72(1), 30–71 (2013)MathSciNetCrossRefMATH
Metadaten
Titel
Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
verfasst von
Seok-Hee Hong
Hiroshi Nagamochi
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-50106-2_25