D 2017

Two-layer Drawings of Bipartite Graphs

DIWAN, Ajit Arvind; Bodhayan ROY a Subir Kumar GHOSH

Základní údaje

Originální název

Two-layer Drawings of Bipartite Graphs

Autoři

DIWAN, Ajit Arvind; Bodhayan ROY a Subir Kumar GHOSH

Vydání

Eurocomb 2017. od s. 351-357, 7 s. 2017

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

Informatika

Utajení

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

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

abstract topological graph; two-layer drawing; bipartite graph

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 10. 4. 2018 10:45, Bodhayan Roy, Ph.D.

Anotace

V originále

We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.