Abstract
Point-set embeddings and large-angle crossings are two areas of graph drawing that independently have received a lot of attention in the past few years. In this paper, we consider problems in the intersection of these two areas. Given the point-set-embedding scenario, we are interested in how much we gain in terms of computational complexity, curve complexity, and generality if we allow large-angle crossings as compared to the planar case.
We investigate two drawing styles where only bends or both bends and edges must be drawn on an underlying grid. We present various results for drawings with one, two, and three bends per edge.
Part of this research has been presented as a poster at the 19th Int. Symposium on Graph Drawing, Eindhoven, 2011.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arikushi, K., Fulek, R., Keszegh, B., Morić, F., Tóth, C.: Graphs that Admit Right Angle Crossing Drawings. In: WG 2010. LNCS, vol. 6410, pp. 135–146. Springer, Heidelberg (2010)
Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Alg. Appl. 10(2), 353–366 (2006)
Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory Comput. Syst. 49(3), 565–575 (2011)
Di Giacomo, E., Frati, F., Fulek, R., Grilli, L., Krug, M.: Orthogeodesic Point-set Embedding of Trees. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS. Springer, Heidelberg (to appear, 2012)
Didimo, W., Eades, P., Liotta, G.: Drawing Graphs with Right Angle Crossings. In: Dehne, F., Gavrilova, M.L., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009)
Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691–703 (1976)
Fink, M., Haunert, J.H., Mchedlidze, T., Spoerhase, J., Wolff, A.: Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. ArXiv e-print abs/1107.4970v1 (2011)
Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom. 42(4), 542–569 (2009)
Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mon. 98, 165–166 (1991)
Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: Proc. 7th Int. IEEE Asia-Pacific Symp. Inform. Visual (APVIS 2008), pp. 41–46 (2008)
Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-Geodesic Embedding of Planar Graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207–218. Springer, Heidelberg (2010)
Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Alg. Appl. 6(1), 115–129 (2002)
Olariu, S.: An optimal greedy heuristic to color interval graphs. Inform. Process. Lett. 37(1), 21–25 (1991)
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs Combin. 17(4), 717–728 (2001)
Papakostas, A., Tollis, I.G.: Efficient orthogonal drawings of high degree graphs. Algorithmica 26, 100–125 (2000)
Raghavan, R., Cohoon, J., Sahni, S.: Single bend wiring. J. Algorithms 7(2), 232–257 (1986)
Rendl, F., Woeginger, G.: Reconstructing sets of orthogonal line segments in the plane. Discrete Math. 119, 167–174 (1993)
Skulrattanakulchai, S.: 4-edge-coloring graphs of maximum degree 3 in linear time. Inform. Process. Lett. 81(4), 191–195 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fink, M., Haunert, JH., Mchedlidze, T., Spoerhase, J., Wolff, A. (2012). Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. In: Rahman, M.S., Nakano, Si. (eds) WALCOM: Algorithms and Computation. WALCOM 2012. Lecture Notes in Computer Science, vol 7157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28076-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-28076-4_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28075-7
Online ISBN: 978-3-642-28076-4
eBook Packages: Computer ScienceComputer Science (R0)