Short Plane Supports for Spatial Hypergraphs

Castermans, Thom; van Garderen, Mereke; Meulemans, Wouter; Nöllenburg, Martin; Yuan, Xiaoru

Short Plane Supports for Spatial Hypergraphs

Dateien

Castermans_2-1ewgermpem5ln9.pdfGröße: 2.75 MBDownloads: 73

Datum

2019

Autor:innen

Castermans, Thom

van Garderen, Mereke

Meulemans, Wouter

Nöllenburg, Martin

Yuan, Xiaoru

Open Access-Veröffentlichung

Open Access Gold

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Journal of Graph Algorithms and Applications. European Mathematical Society (EMS). 2019, 23(3), pp. 463-498. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00499

Zusammenfassung

A graph G = (V;E) is a support of a hypergraph H = (V; S) if every hyperedge induces a connected subgraph in G. Supports are used for cer- tain types of hypergraph drawings, also known as set visualizations. In this paper we consider visualizing spatial hypergraphs, where each ver- tex has a fixed location in the plane. This scenario appears when, e.g., modeling set systems of geospatial locations as hypergraphs. Following established aesthetic quality criteria, we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V . From a theoretical point of view, we first show that the problem is NP-hard already under rather mild conditions, and additionally provide a negative approximability result. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Fur- thermore, we evaluate the performance and trade-offs between solution quality and speed of heuristics relative to each other and compared to optimal solutions.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

CASTERMANS, Thom, Mereke VAN GARDEREN, Wouter MEULEMANS, Martin NÖLLENBURG, Xiaoru YUAN, 2019. Short Plane Supports for Spatial Hypergraphs. In: Journal of Graph Algorithms and Applications. European Mathematical Society (EMS). 2019, 23(3), pp. 463-498. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00499

BibTex

@article{Castermans2019Short-57309,
  year={2019},
  doi={10.7155/jgaa.00499},
  title={Short Plane Supports for Spatial Hypergraphs},
  number={3},
  volume={23},
  journal={Journal of Graph Algorithms and Applications},
  pages={463--498},
  author={Castermans, Thom and van Garderen, Mereke and Meulemans, Wouter and Nöllenburg, Martin and Yuan, Xiaoru}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/57309">
    <dcterms:issued>2019</dcterms:issued>
    <dc:language>eng</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-04-19T16:30:33Z</dc:date>
    <dcterms:abstract xml:lang="eng">A graph G = (V;E) is a support of a hypergraph H = (V; S) if every hyperedge induces a connected subgraph in G. Supports are used for cer- tain types of hypergraph drawings, also known as set visualizations. In this paper we consider visualizing spatial hypergraphs, where each ver- tex has a fixed location in the plane. This scenario appears when, e.g., modeling set systems of geospatial locations as hypergraphs. Following established aesthetic quality criteria, we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V . From a theoretical point of view, we first show that the problem is NP-hard already under rather mild conditions, and additionally provide a negative approximability result. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Fur- thermore, we evaluate the performance and trade-offs between solution quality and speed of heuristics relative to each other and compared to optimal solutions.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/57309/1/Castermans_2-1ewgermpem5ln9.pdf"/>
    <dc:creator>Castermans, Thom</dc:creator>
    <dc:creator>Yuan, Xiaoru</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>terms-of-use</dc:rights>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>van Garderen, Mereke</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:creator>Nöllenburg, Martin</dc:creator>
    <dc:contributor>Nöllenburg, Martin</dc:contributor>
    <dcterms:title>Short Plane Supports for Spatial Hypergraphs</dcterms:title>
    <dc:contributor>van Garderen, Mereke</dc:contributor>
    <dc:creator>Meulemans, Wouter</dc:creator>
    <dc:contributor>Meulemans, Wouter</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/57309/1/Castermans_2-1ewgermpem5ln9.pdf"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/57309"/>
    <dc:contributor>Yuan, Xiaoru</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-04-19T16:30:33Z</dcterms:available>
    <dc:contributor>Castermans, Thom</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Begutachtet

Ja