Information Technology Reference
In-Depth Information
7
Open Questions
We want to conclude with a list of open questions:
What is the complexity of recognizinggraphs admitting UPCRs with regular poly-
gons other than squares?
Can we characterize the graphs with USqPCRs? Or with other polygons?
Do the trihexagonal and truncated trihexagonal grid admit a USqPCR?
Do subgraphs of duals of Archimedean grids not containing
K
1
,
9
have UCuPCR?
What aboutUSqPCR for duals not containing
K
1
,
5
, namely the snubsquare grid?
References
[1] Alam, M.J., Kobourov, S.G., Pupyrev, S., Toeniskoetter, J.: Happy edges: Threshold-
coloring of regular lattices. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS,
vol. 8496, pp. 28-39. Springer, Heidelberg (2014)
[2] Alam, M.J., Chaplick, S., Fijavz, G., Kaufmann, M., Kobourov, S.G., Pupyrev, S.:
Threshold-coloring and unit-cube contact representation of graphs. In: Brandstadt, A.,
Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 26-37. Springer, Heidel-
berg (2013)
[3] Bremner, D., Evans, W., Frati, F., Heyer, L., Kobourov, S.G., Lenhart, W.J., Liotta, G.,
Rappaport, D., Whitesides, S.H.: On representinggraphs by touching cuboids. In: Didimo,
W. , Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 187-198. Springer, Heidelberg
(2013)
[4] Breu, H., Kirkpatrick, D.G.: On the complexity of recognizing intersection and touching
graphs of disks. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 88-98. Springer,
Heidelberg (1996)
[5] Czyzowicz, J., Kranakis, E., Krizanc, D., Urrutia, J.: Discrete realizations of contact and in-
tersection graphs. International Journal of Pure and Applied Mathematics 13(4), 429 (2004)
[6] Felsner, S., Francis, M.C.: Contact representations of planar graphs with cubes. In: Pro-
ceedings of the 27th Annual ACM SymposiumonComputational Geometry, pp. 315-320.
ACM (2011)
[7] Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation
of planar graphs. In: L opez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 417-432.
Springer, Heidelberg (2010)
[8] Gon¸alves, D., Leveque, B., Pinlou,A.:Triangle contact representations and duality. Dis-
crete & Computational Geometry 48(1), 239-254 (2012)
[9] Hlineny, P., Kratochvıl, J.: Representinggraphs by disks and balls (a survey of recognition-
complexity results). Discrete Mathematics 229(1-3), 101-124 (2001)
[10] Koebe, P.: Kontaktprobleme der konformen abbildung.Berichteuber die Verhandlungen
der Sachsischen Akademien der Wissenschaften zu Leipzig,Math.-Phys. Kl. 88, 141-164
(1936)
[11] Schramm, O.: Combinatorically prescribed packings and applications to conformal and qua-
siconformal maps. Ph. D. thesis. Princeton University (1990)
[12] Schramm, O.: Square tilings with prescribed combinatorics. Israel Journal of Mathemat-
ics 84(1-2), 97-118 (1993)
[13] Zhao, L.: The kissing number of the regular polygon. Discrete Mathematics 188(1), 293-
296 (1998)
[14] Zhao, L., Xu, J.: The kissing number of the regular pentagon. Discrete Mathematics 252(1),
293-298 (2002)
