On Strict (Outer-)Confluent Graphs

D 2019

On Strict (Outer-)Confluent Graphs

FORSTER, Henry, Robert GANIAN, Fabian KLUTE and Martin NOLLENBURG

Basic information

Original name

On Strict (Outer-)Confluent Graphs

Authors

FORSTER, Henry (840 United States of America), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Fabian KLUTE (276 Germany) and Martin NOLLENBURG (276 Germany)

Edition

USA, Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, p. 147-161, 15 pp. 2019

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/19:00113723

Organization unit

Faculty of Informatics

ISBN

978-3-030-35801-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-35802-0_12

UT WoS

000612918800012

Keywords in English

Parameterized Complexity

Abstract

V originále

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like (delta-)SOC graphs have bounded cliquewidth.

Citovat

FORSTER, Henry, Robert GANIAN, Fabian KLUTE and Martin NOLLENBURG. On Strict (Outer-)Confluent Graphs. Online. In Daniel Archambault, Csaba D. Toth. Graph Drawing and Network Visualization - 27th International Symposium, GD 2019. USA: Springer, 2019, p. 147-161. ISBN 978-3-030-35801-3. Available from: https://dx.doi.org/10.1007/978-3-030-35802-0_12.

@inproceedings{1648260,
   author = {Forster, Henry and Ganian, Robert and Klute, Fabian and Nollenburg, Martin},
   address = {USA},
   booktitle = {Graph Drawing and Network Visualization - 27th International Symposium, GD 2019},
   doi = {http://dx.doi.org/10.1007/978-3-030-35802-0_12},
   editor = {Daniel Archambault, Csaba D. Toth},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-3-030-35801-3},
   pages = {147-161},
   publisher = {Springer},
   title = {On Strict (Outer-)Confluent Graphs},
   url = {https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_12},
   year = {2019}
}

TY  - JOUR
ID  - 1648260
AU  - Forster, Henry - Ganian, Robert - Klute, Fabian - Nollenburg, Martin
PY  - 2019
TI  - On Strict (Outer-)Confluent Graphs
PB  - Springer
CY  - USA
SN  - 9783030358013
KW  - Parameterized Complexity
UR  - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_12
L2  - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_12
N2  - A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like (delta-)SOC graphs have bounded cliquewidth.
ER  -

FORSTER, Henry, Robert GANIAN, Fabian KLUTE and Martin NOLLENBURG. On Strict (Outer-)Confluent Graphs. Online. In Daniel Archambault, Csaba D. Toth. \textit{Graph Drawing and Network Visualization - 27th International Symposium, GD 2019}. USA: Springer, 2019, p.~147-161. ISBN~978-3-030-35801-3. Available from: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}12.

Detailed Information on Publication Record