Search

Your search keyword '"Kratochvíl, Jan"' showing total 155 results
Start Over Author "Kratochvíl, Jan" Search Limiters Peer Reviewed
155 results on '"Kratochvíl, Jan"'

3. List covering of regular multigraphs with semi-edges

Author

Bok, Jan, Fiala, Jiří, Jedličková, Nikola, Kratochvíl, Jan, and Rzążewski, Paweł

Subjects
Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-edges}. A graph is called {\em simple} if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph $H$ of valency greater than 2, deciding if an input graph covers $H$ is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called \textsc{List-$H$-Cover}, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the \textsc{List-$H$-Cover} problem is NP-complete for every regular graph $H$ of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of \textsc{ List-$H$-Cover} for cubic graphs., Comment: full version, submited to a journal

Published
2022
Full Text
View/download PDF

6. Cops and Robbers on Intersection Graphs

Author

Gavenčiak, Tomáš, Gordinowicz, Przemysław, Jelínek, Vít, Klavík, Pavel, and Kratochvíl, Jan

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Abstract

The cop number of a graph $G$ is the smallest $k$ such that $k$ cops win the game of cops and robber on $G$. We investigate the maximum cop number of geometric intersection graphs, which are graphs whose vertices are represented by geometric shapes and edges by their intersections. We establish the following dichotomy for previously studied classes of intersection graphs: The intersection graphs of arc-connected sets in the plane (called string graphs) have cop number at most 15, and more generally, the intersection graphs of arc-connected subsets of a surface have cop number at most $10g+15$ in case of orientable surface of genus $g$, and at most $10g'+15$ in case of non-orientable surface of Euler genus $g'$. For more restricted classes of intersection graphs, we obtain better bounds: the maximum cop number of interval filament graphs is two, and the maximum cop number of outer-string graphs is between 3 and 4. The intersection graphs of disconnected 2-dimensional sets or of 3-dimensional sets have unbounded cop number even in very restricted settings. For instance, we show that the cop number is unbounded on intersection graphs of two-element subsets of a line, as well as on intersection graphs of 3-dimensional unit balls, of 3-dimensional unit cubes or of 3-dimensional axis-aligned unit segments.

Published
2016
Full Text
View/download PDF

17. Drawing Simultaneously Embedded Graphs with Few Bends.

Author

Grilli, Luca, Hong, Seok-Hee, Kratochvíl, Jan, and Rutter, Ignaz

Subjects
ALGORITHMS
Abstract

We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (SEFE) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (SGE) for a non-trivial class of graphs. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results