@inproceedings{ca6d2acef40d41bdbeaf2709d7a3e011,
title = "Using the Metro-Map Metaphor for Drawing Hypergraphs",
abstract = "For a planar graph G and a set Π of simple paths in G, we define a metro-map embedding to be a planar embedding of G and an ordering of the paths of Π along each edge of G. This definition of a metro-map embedding is motivated by visual representations of hypergraphs using the metro-map metaphor. In a metro-map embedding, two paths cross in a so-called vertex crossing if they pass through the vertex and alternate in the circular ordering around it. We study the problem of constructing metro-map embeddings with the minimum number of crossing vertices, that is, vertices where paths cross. We show that the corresponding decision problem is NP-complete for general planar graphs but can be solved efficiently for trees or if the number of crossing vertices is constant. All our results hold both in a fixed and variable embedding settings.",
keywords = "Clustered planarity, Crossing minimization, Hypergraph visualization, Metro-map metaphor, NP-hardness",
author = "Fabian Frank and Michael Kaufmann and Stephen Kobourov and Tamara Mchedlidze and Sergey Pupyrev and Torsten Ueckerdt and Alexander Wolff",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 ; Conference date: 25-01-2021 Through 29-01-2021",
year = "2021",
doi = "10.1007/978-3-030-67731-2_26",
language = "English (US)",
isbn = "9783030677305",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "361--372",
editor = "Tom{\'a}{\v s} Bure{\v s} and Riccardo Dondi and Johann Gamper and Giovanna Guerrini and Tomasz Jurdzinski and Claus Pahl and Florian Sikora and Wong, {Prudence W.}",
booktitle = "SOFSEM 2021",
address = "Germany",
}