Abstract
In this paper we study two problems related to the drawing of level graphs, that is, T -Level Planarity and Clustered-Level Planarity. We show that both problems are \(\mathcal{NP}\)-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Angelini, P., Da Lozzo, G., Neuwirth, D.: On the complexity of some problems related to SEFE. CoRR abs/1207.3934 (2013)
Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. J. of Discrete Algorithms 14, 150–172 (2012)
Angelini, P., Da Lozzo, G.: Deepening the relationship between SEFE and C-planarity. CoRR abs/1404.6175 (2014)
Angelini, P., Da Lozzo, G., Neuwirth, D.: On some \(\mathcal{NP}\)-complete SEFE problems. In: Pal, S.P., Sadakane, K. (eds.) WALCOM 2014. LNCS, vol. 8344, pp. 200–212. Springer, Heidelberg (2014)
Blasiüs, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)
Bläsius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 31–42. Springer, Heidelberg (2013)
Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: Khanna, S. (ed.) SODA, pp. 1030–1043. SIAM (2013)
Eades, P., Feng, Q.W., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)
Forster, M., Bachmaier, C.: Clustered level planarity. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 218–228. Springer, Heidelberg (2004)
Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1999)
Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111–114 (1979)
Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. of Graph Alg. and Appl. 17(4), 367–440 (2013)
Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation. Discrete Applied Mathematics 160(16-17), 2349–2363 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V. (2014). The Importance of Being Proper. In: Duncan, C., Symvonis, A. (eds) Graph Drawing. GD 2014. Lecture Notes in Computer Science, vol 8871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45803-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-662-45803-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45802-0
Online ISBN: 978-3-662-45803-7
eBook Packages: Computer ScienceComputer Science (R0)