Using the Metro-Map Metaphor for Drawing Hypergraphs

摘要

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.