On Strict (Outer-)Confluent Graphs

D 2019

On Strict (Outer-)Confluent Graphs

FORSTER, Henry; Robert GANIAN; Fabian KLUTE a Martin NOLLENBURG

Základní údaje

Originální název

On Strict (Outer-)Confluent Graphs

Autoři

FORSTER, Henry (840 Spojené státy); Robert GANIAN (203 Česká republika, garant, domácí); Fabian KLUTE (276 Německo) a Martin NOLLENBURG (276 Německo)

Vydání

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

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00113723

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-35801-3

ISSN

DOI

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

UT WoS

000612918800012

EID Scopus

2-s2.0-85076877772

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 16. 5. 2022 14:30, Mgr. Michal Petr

Anotace

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 a 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, s. 147-161. ISBN 978-3-030-35801-3. Dostupné z: 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  - CONF
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 a 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, s.~147-161. ISBN~978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}12.

Přehled o publikaci