Skip to main content

2015 | OriginalPaper | Buchkapitel

Recognizing Weighted Disk Contact Graphs

verfasst von : Boris Klemz, Martin Nöllenburg, Roman Prutkin

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

Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be \(\textsf {NP}\)-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains \(\textsf {NP}\)-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.

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 Alam, M.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Pupyrev, S.: Balanced circle packings for planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 125–136. Springer, Heidelberg (2014) Alam, M.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Pupyrev, S.: Balanced circle packings for planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 125–136. Springer, Heidelberg (2014)
2.
Zurück zum Zitat Bowen, C., Durocher, S., Löffler, M., Rounds, A., Schulz, A., Tóth, C.D.: Realization of simply connected polygonal linkages and recognition of unit disk contact trees. In: Di Giacomo, E., Lubiw, A. (eds.) Graph Drawing (GD’15). LNCS, vol. 9411, pp. 447–459. Springer, Heidelberg (2015) Bowen, C., Durocher, S., Löffler, M., Rounds, A., Schulz, A., Tóth, C.D.: Realization of simply connected polygonal linkages and recognition of unit disk contact trees. In: Di Giacomo, E., Lubiw, A. (eds.) Graph Drawing (GD’15). LNCS, vol. 9411, pp. 447–459. Springer, Heidelberg (2015)
3.
6.
Zurück zum Zitat Di Giacomo, E., Didimo, W., Hong, S.H., Kaufmann, M., Kobourov, S., Liotta, G., Misue, K., Symvonis, A., Yen, H.C.: Low ply graph drawing. In: IISA 2015. IEEE (to appear, 2015) Di Giacomo, E., Didimo, W., Hong, S.H., Kaufmann, M., Kobourov, S., Liotta, G., Misue, K., Symvonis, A., Yen, H.C.: Low ply graph drawing. In: IISA 2015. IEEE (to appear, 2015)
7.
Zurück zum Zitat Dorling, D.: Area cartograms: Their use and creation. In: Concepts and techniques in modern geography. University of East Anglia: Environmental Publications (1996) Dorling, D.: Area cartograms: Their use and creation. In: Concepts and techniques in modern geography. University of East Anglia: Environmental Publications (1996)
8.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \({ NP}\)-Completeness. W. H. Freeman & Co., New York (1990) Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \({ NP}\)-Completeness. W. H. Freeman & Co., New York (1990)
9.
Zurück zum Zitat Hale, W.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980)CrossRef Hale, W.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980)CrossRef
10.
Zurück zum Zitat Inoue, R.: A new construction method for circle cartograms. Cartography Geogr. Inf. Sci. 38(2), 146–152 (2011)CrossRef Inoue, R.: A new construction method for circle cartograms. Cartography Geogr. Inf. Sci. 38(2), 146–152 (2011)CrossRef
11.
12.
13.
Zurück zum Zitat Koebe, P.: Kontaktprobleme der konformen Abbildung. In: Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse, vol. 88, pp. 141–164 (1936) Koebe, P.: Kontaktprobleme der konformen Abbildung. In: Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse, vol. 88, pp. 141–164 (1936)
16.
Zurück zum Zitat Robert, J.M., Toussaint, G.: Computational geometry and facility location. In: Operations Research and Management Science, pp. 11–15 (1990) Robert, J.M., Toussaint, G.: Computational geometry and facility location. In: Operations Research and Management Science, pp. 11–15 (1990)
17.
18.
Zurück zum Zitat Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)CrossRef Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)CrossRef
Metadaten
Titel
Recognizing Weighted Disk Contact Graphs
verfasst von
Boris Klemz
Martin Nöllenburg
Roman Prutkin
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-27261-0_36