Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes; Hans L. Bodlaender; Gunther Cornelissen; Marieke van der Wegen

doi:10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes
, Hans L. Bodlaender
, Gunther Cornelissen
, Marieke van der Wegen

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

Abstract

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(nlog n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
Editors	Andreas Brandstädt, Ekkehard Köhler, Klaus Meer
Place of Publication	Cham
Publisher	Springer
Pages	52-64
Number of pages	13
ISBN (Electronic)	978-3-030-00256-5
ISBN (Print)	978-3-030-00255-8
DOIs	https://doi.org/10.1007/978-3-030-00256-5_5
Publication status	Published - 1 Jan 2018
Event	44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany Duration: 27 Jun 2018 → 29 Jun 2018 https://www.wg2018.b-tu.de/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11159 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Abbreviated title	WG2018
Country/Territory	Germany
City	Cottbus
Period	27/06/18 → 29/06/18
Internet address	https://www.wg2018.b-tu.de/

Access to Document

10.1007/978-3-030-00256-5_5

Cite this

Bodewes, J. M., Bodlaender, H. L., Cornelissen, G., & van der Wegen, M. (2018). Recognizing hyperelliptic graphs in polynomial time. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings (pp. 52-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS). Springer. https://doi.org/10.1007/978-3-030-00256-5_5

Bodewes, Jelco M. ; Bodlaender, Hans L. ; Cornelissen, Gunther et al. / Recognizing hyperelliptic graphs in polynomial time. Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. editor / Andreas Brandstädt ; Ekkehard Köhler ; Klaus Meer. Cham : Springer, 2018. pp. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dd0845136d134a46b2470212ec8eebb4,

title = "Recognizing hyperelliptic graphs in polynomial time",

abstract = "Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(nlog n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.",

author = "Bodewes, \{Jelco M.\} and Bodlaender, \{Hans L.\} and Gunther Cornelissen and \{van der Wegen\}, Marieke",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-00256-5\_5",

language = "English",

isbn = "978-3-030-00255-8",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "52--64",

editor = "Andreas Brandst{\"a}dt and Ekkehard K{\"o}hler and Klaus Meer",

booktitle = "Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings",

address = "Germany",

note = "44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018), WG2018 ; Conference date: 27-06-2018 Through 29-06-2018",

url = "https://www.wg2018.b-tu.de/",

}

Bodewes, JM, Bodlaender, HL, Cornelissen, G & van der Wegen, M 2018, Recognizing hyperelliptic graphs in polynomial time. in A Brandstädt, E Köhler & K Meer (eds), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11159 LNCS, Springer, Cham, pp. 52-64, 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018), Cottbus, Germany, 27/06/18. https://doi.org/10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time. / Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther et al.
Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. ed. / Andreas Brandstädt; Ekkehard Köhler; Klaus Meer. Cham: Springer, 2018. p. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Recognizing hyperelliptic graphs in polynomial time

AU - Bodewes, Jelco M.

AU - Bodlaender, Hans L.

AU - Cornelissen, Gunther

AU - van der Wegen, Marieke

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(nlog n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

AB - Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(nlog n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

UR - https://www.scopus.com/pages/publications/85053475695

U2 - 10.1007/978-3-030-00256-5_5

DO - 10.1007/978-3-030-00256-5_5

M3 - Conference contribution

AN - SCOPUS:85053475695

SN - 978-3-030-00255-8

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 52

EP - 64

BT - Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings

A2 - Brandstädt, Andreas

A2 - Köhler, Ekkehard

A2 - Meer, Klaus

PB - Springer

CY - Cham

T2 - 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)

Y2 - 27 June 2018 through 29 June 2018

ER -

Bodewes JM, Bodlaender HL, Cornelissen G, van der Wegen M. Recognizing hyperelliptic graphs in polynomial time. In Brandstädt A, Köhler E, Meer K, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Cham: Springer. 2018. p. 52-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this