OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

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

ACM Ref: TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, MathematicsofComputing_DISCRETEMATHEMATICS
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

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok