16 citations · 94 across the 30 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.LO2018
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
math.CO2018
On Degree Properties of Crossing-Critical Families of Graphs
Drago Bokal, Mojca Bračič, Marek Derňár +1
Answering an open question from 2007, we construct infinite -crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~…
math.CO2018★ 4 cited
Structure and generation of crossing-critical graphs
Zdeněk Dvořák, Petr Hliněný, Bojan Mohar
We study -crossing-critical graphs, which are the minimal graphs that require at least edge-crossings when drawn in the plane. For there are only two such graphs witho…