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:
Cryptography in a Quantum World Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Orthogonal Layout with Optimal Face Complexity

verfasst von : M. Jawaherul Alam, Stephen G. Kobourov, Debajyoti Mondal

Erschienen in: SOFSEM 2016: Theory and Practice of Computer Science

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We study a problem motivated by rectilinear schematization of geographic maps. Given a biconnected plane graph G and an integer \(k\ge 0\), does G have a strict-orthogonal drawing with at most k reflex angles per face? For \(k=0\) the problem is equivalent to realizing each face as a rectangle. The problem can be reduced to a max-flow problem in some linear-size nonplanar network, but the best solutions require \(\varOmega (n^{1.5} \log n\log k)\) time. We describe a graph matching approach that can decide strict-orthogonal drawability for arbitrary reflex complexity k in \(O((nk)^{1.5})\) time, which is faster for constant values of k. In contrast, if the embedding is not fixed, we prove that it is NP-complete to decide whether a planar graph admits a strict-orthogonal drawing with reflex face complexity 4.

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 On Contact Graphs with Cubes and Proportional Boxes
Nächstes Kapitel L-Drawings of Directed Graphs
Literatur
1.
Bläsius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with flexibility constraints. Algorithmica 68(4), 859–885 (2014)MATHMathSciNetCrossRef
2.
Bläsius, T., Rutter, I., Wagner, D.: Optimal orthogonal graph drawing with convex bend costs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 184–195. Springer, Heidelberg (2013)CrossRef
3.
Chimani, M., Gutwenger, C., Jünger, M., Klau, G., Klein, K., Mutzel, P.: The open graph drawing framework. In: Handbook of Graph Drawing and Visualization, pp. 543–571 (2013)
4.
5.
de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187–206 (2012)MATHCrossRef
6.
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs, 3rd edn. The MIT Press, Cambridge (2009)
7.
Ellson, J., Gansner, E.R., Koutsofios, L., North, S.C., Woodhull, G.: Graphviz—open source graph drawing tools. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, p. 483. Springer, Heidelberg (2002)CrossRef
8.
Fößmeier, U., Kaufmann, M.: Drawing high degree graphs with low bend numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 254–266. Springer, Heidelberg (1996)CrossRef
9.
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)MATHMathSciNetCrossRef
10.
Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)MATHMathSciNetCrossRef
11.
Kaufmann, M., Wagner, D.: Drawing Graphs: Methods and Models. LNCS, vol. 2025. Springer, London (2001)CrossRef
12.
13.
Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Symposium on Foundations of Computer Science (FOCS), pp. 270–281 (1980)
14.
Leiserson, C.E., Cormen, T.H., Stein, C., Rivest, R.: Introduction to Algorithms. Prentice Hall, Englewood Cliffs (1999)
15.
Miura, K., Haga, H., Nishizeki, T.: Inner rectangular drawings of plane graphs. Int. J. Comput. Geom. Appl. 16(2–3), 249–270 (2006)MATHMathSciNetCrossRef
16.
Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Singapore (2004)MATHCrossRef
17.
Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. 88–D(1), 23–30 (2005)
18.
19.
Tobler, W.: Thirty five years of computer cartograms. Ann. Assoc. Am. Geogr. 94, 58–73 (2004)CrossRef
20.
21.
Wiese, R., Eiglsperger, M., Kaufmann, M.: yFiles: visualization and automatic layout of graphs. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 453–454. Springer, Heidelberg (2002)CrossRef
Metadaten
Titel
Orthogonal Layout with Optimal Face Complexity
verfasst von
M. Jawaherul Alam
Stephen G. Kobourov
Debajyoti Mondal
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
SOFSEM 2016: Theory and Practice of Computer Science

Print ISBN: 978-3-662-49191-1

Electronic ISBN: 978-3-662-49192-8

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49192-8_10