Publikation: Automorphism Faithfulness Metrics for Symmetric Graph Drawings
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
In this paper, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are faithfulness metrics, i.e., they measure how faithfully a drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational), and (2) a group of geometric automorphisms (cyclic or dihedral). We present algorithms to compute the automorphism faithfulness metrics in O(n log n) time. Moreover, we also present efficient algorithms to detect exact symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
MEIDIANA, Amyra, Seok-Hee HONG, Peter EADES, Daniel A. KEIM, 2022. Automorphism Faithfulness Metrics for Symmetric Graph Drawings. In: IEEE Transactions on Visualization and Computer Graphics. IEEE. ISSN 1077-2626. eISSN 1941-0506. Available under: doi: 10.1109/TVCG.2022.3229354BibTex
@article{Meidiana2022Autom-59573, year={2022}, doi={10.1109/TVCG.2022.3229354}, title={Automorphism Faithfulness Metrics for Symmetric Graph Drawings}, issn={1077-2626}, journal={IEEE Transactions on Visualization and Computer Graphics}, author={Meidiana, Amyra and Hong, Seok-Hee and Eades, Peter and Keim, Daniel A.} }
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/59573"> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:contributor>Hong, Seok-Hee</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59573"/> <dc:creator>Meidiana, Amyra</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Eades, Peter</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:creator>Hong, Seok-Hee</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-12-20T12:12:58Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>Automorphism Faithfulness Metrics for Symmetric Graph Drawings</dcterms:title> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Eades, Peter</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-12-20T12:12:58Z</dcterms:available> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59573/1/Meidiana_2-nbs8sjarj8fu1.pdf"/> <dc:contributor>Keim, Daniel A.</dc:contributor> <dcterms:abstract xml:lang="eng">In this paper, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are faithfulness metrics, i.e., they measure how faithfully a drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational), and (2) a group of geometric automorphisms (cyclic or dihedral). We present algorithms to compute the automorphism faithfulness metrics in O(n log n) time. Moreover, we also present efficient algorithms to detect exact symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.</dcterms:abstract> <dc:contributor>Meidiana, Amyra</dc:contributor> <dc:creator>Keim, Daniel A.</dc:creator> <dc:rights>terms-of-use</dc:rights> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59573/1/Meidiana_2-nbs8sjarj8fu1.pdf"/> <dcterms:issued>2022</dcterms:issued> </rdf:Description> </rdf:RDF>