35 citations · 100 across the 23 of their papers we have counts for
5 papers · 1 filter
The Rique-Number of Graphs
Michael A. Bekos, Stefan Felsner, Philipp Kindermann +3
We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find a linear order of the vertices…
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Jan Kratochvíl, Tomáš Masařík, Jana Novotná
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, the…
On Vertex- and Empty-Ply Proximity Drawings
Patrizio Angelini, Steven Chaplick, Felice De Luca +7
We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equ…
Extending partial representations of function graphs and permutation graphs
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk +1
Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability gra…
MSOL Restricted Contractibility to Planar Graphs
James Abello, Pavel Klavík, Jan Kratochvíl +1
We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set of at most edges that when contracte…