Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
GraphMaps: Browsing Large Graphs as Interactive Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

A Universal Point Set for 2-Outerplanar Graphs

Authors : Patrizio Angelini, Till Bruckdorfer, Michael Kaufmann, Tamara Mchedlidze

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

A point set \(S \subseteq \mathbb {R}^2\) is universal for a class \(\mathcal G\) if every graph of \(\mathcal{G}\) has a planar straight-line embedding on S. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size \(O(n \log n)\).

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 On Embeddability of Buses in Point Sets
next chapter Linear-Size Universal Point Sets for One-Bend Drawings
Footnotes
1
The distribution of the points into dense and sparse portions of the point set is inspired by [1].
 
Literature
1.
Angelini, P., Di Battista, G., Kaufmann, M., Mchedlidze, T., Roselli, V., Squarcella, C.: Small point sets for simply-nested planar graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 75–85. Springer, Heidelberg (2011) CrossRef
2.
Angelini, P., Bruckdorfer, T., Kaufmann, M., Mchedlidze, T.: A universal point set for 2-outerplanar graphs (2015). CoRR abs/​1508.​05784
3.
Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl. 18(2), 177–209 (2014)MathSciNetCrossRefMATH
4.
Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. CGTA 43, 219–232 (2010)MATH
5.
Bose, P.: On embedding an outer-planar graph in a point set. CGTA 23(3), 303–312 (2002)MATH
6.
Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353–366 (2006)MathSciNetCrossRefMATH
7.
de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fáry embeddings of planar graphs. In: Simon, J. (ed.) STOC ’88, pp. 426–433. ACM (1988)
8.
9.
10.
Gritzmann, P., Pach, B.M.J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Am. Math. Monthly 98, 165–166 (1991)MathSciNetCrossRef
11.
Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inf. Process. Lett. 92(2), 95–98 (2004)MathSciNetCrossRefMATH
12.
Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) SODA ’90, pp. 138–148. SIAM (1990)
Metadata
Title
A Universal Point Set for 2-Outerplanar Graphs
Authors
Patrizio Angelini
Till Bruckdorfer
Michael Kaufmann
Tamara Mchedlidze
Copyright Year
2015
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_34

Premium Partner

    Image Credits