Recognizing Weighted Disk Contact Graphs

Klemz, Boris and Nöllenburg, Martin and Prutkin, Roman (2015) Recognizing Weighted Disk Contact Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 433-446 (Official URL:

Full text not available from this repository.


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 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 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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
P Styles > P.999 Others
Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
ID Code:1510

Repository Staff Only: item control page


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)

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)

Breu, H., Kirkpatrick, D.G.: Unit disk graph recognitionis NP-hard. Comput. Geom. 9(1–2), 3–24 (1998)

Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1–3), 165–177 (1990)

Collins, C.R., Stephenson, K.: A circle packing algorithm. Comput. Geom. 25(3), 233–256 (2003)

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)

Dorling, D.: Area cartograms: Their use and creation. In: Concepts and techniques in modern geography. University of East Anglia: Environmental Publications (1996)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)

Hale, W.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980)

Inoue, R.: A new construction method for circle cartograms. Cartography Geogr. Inf. Sci. 38(2), 146–152 (2011)

Klemz, B., Nöllenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs, September 2015. CoRR arXiv:​1509.​0072

Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)

Koebe, P.: Kontaktprobleme der konformen Abbildung. In: Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse, vol. 88, pp. 141–164 (1936)

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

Mohar, B.: A polynomial time circle packing algorithm. Discrete Math. 117(1), 257–263 (1993)

Robert, J.M., Toussaint, G.: Computational geometry and facility location. In: Operations Research and Management Science, pp. 11–15 (1990)

Stephenson, K.: Circle packing: a mathematical tale. Not. AMS 50(11), 1376–1388 (2003)

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)