11 citations · 17 across the 10 of their papers we have counts for
16 papers
On the Weisfeiler-Leman dimension of some polyhedral graphs
Haiyan Li, Ilia Ponomarenko, Peter Zeman
Let be a positive integer, a graph with vertex set , and the coloring of the Cartesian -power , obtained by the -dimensional Weisfeiler-Leman…
Beyond circular-arc graphs -- recognizing lollipop graphs and medusa graphs
Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz +5
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph , the class of -graphs, defined as the intersection graphs of connected subgraphs of some subdivisio…
Recognition and Isomorphism of Proper -graphs in FPT-time
Deniz Ağaoğlu Çağırıcı, Peter Zeman
An -graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph . Many important classes of graphs, including interval graphs, circular-a…
Extending Partial Representations of Circular-Arc Graphs
Jiří Fiala, Ignaz Rutter, Peter Stumpf +1
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as…
Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
Vikraman Arvind, Roman Nedela, Ilia Ponomarenko +1
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chor…
Automorphism groups of maps in linear time
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela +1
By a map we mean a -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can…