Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams
verfasst von : Boris Klemz, Tamara Mchedlidze, Martin Nöllenburg
Erschienen in: Algorithm Theory – SWAT 2014
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we present an
O
(
n
2
(
m
+ log
n
))-time algorithm for computing a minimum-weight tree support (if one exists) of a hypergraph
H
= (
V
,
S
) with
n
vertices and
m
hyperedges. This improves the previously best known algorithm with running time
O
(
n
4
m
2
). A support of
H
is a graph
G
on
V
such that each hyperedge in
S
induces a connected subgraph in
G
. If
G
is a tree, it is called a tree support and it is a minimum tree support if its edge weight is minimum for a given edge weight function. Tree supports of hypergraphs have several applications, from social network analysis and network design problems to the visualization of hypergraphs and Euler diagrams. We show in particular how a minimum-weight tree support can be used to generate an area-proportional Euler diagram that satisfies typical well-formedness conditions and additionally minimizes the number of concurrent curves of the set boundaries in the Euler diagram.