Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Angelini, Patrizio; Da Lozzo, Giordano; Di Battista, Giuseppe; Frati, Fabrizio; Roselli, Vincenzo (2014)
Languages: English
Types: Preprint
Subjects: Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms

Classified by OpenAIRE into

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 NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. Angelini, P., Da Lozzo, G., Neuwirth, D.: On the complexity of some problems related to SEFE. CoRR abs/1207.3934 (2013)
    • 2. 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)
    • 3. Angelini, P., Da Lozzo, G.: Deepening the relationship between SEFE and C-planarity. CoRR abs/1404.6175 (2014)
    • 4. Angelini, P., Da Lozzo, G., Neuwirth, D.: On some NP-complete SEFE problems. In: Pal, S.P., Sadakane, K. (eds.) WALCOM. LNCS, vol. 8344, pp. 200-212 (2014)
    • 5. Blasiu¨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)
    • 6. Bla¨sius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. In: Didimo, W., Patrignani, M. (eds.) GD'13. LNCS, vol. 7704, pp. 31-42 (2013)
    • 7. Bla¨sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: Khanna, S. (ed.) SODA. pp. 1030-1043. SIAM (2013)
    • 8. 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)
    • 9. Forster, M., Bachmaier, C.: Clustered level planarity. In: van Emde Boas, P., Pokorny´, J., Bielikova´, M., Stuller, J. (eds.) SOFSEM. LNCS, vol. 2932, pp. 218-228 (2004)
    • 10. Ju¨nger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 67-113 (2002)
    • 11. Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111-114 (1979)
    • 12. Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. of Graph Alg. and Appl 17(4), 367-440 (2013)
    • 13. 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)
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects

  • ARC | Discovery Early Career Rese...

Cite this article

Collected from