115 citations · 178 across the 20 of their papers we have counts for
12 papers · 1 filter
3-colorable planar graphs have an intersection segment representation using 3 slopes
Daniel Gonçalves
In his PhD Thesis, E.R. Scheinerman conjectured that planar graphs are intersection graphs of line segments in the plane. This conjecture was proved with two different approaches b…
Contact graphs of boxes with unidirectional contacts
Daniel Gonçalves, Vincent Limouzy, Pascal Ochem
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these gr…
On Comparable Box Dimension
Zdenek Dvorák, Daniel Goncalves, Abhiruk Lahiri +2
Two boxes in are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph is the minimum integer such…
Homothetic triangle representations of planar graphs
Daniel Gonçalves, Benjamin Lévêque, Alexandre Pinlou
We prove that every planar graph is the intersection graph of homothetic triangles in the plane.
Dushnik-Miller dimension of d-dimensional tilings with boxes
Mathew C. Francis, Daniel Gonçalves
Planar graphs are the graphs with Dushnik-Miller dimension at most three (W. Schnyder, Planar graphs and poset dimension, Order 5, 323-343, 1989). Consider the intersection graph o…
Dushnik-Miller dimension of TD-Delaunay complexes
Daniel Gonçalves, Lucas Isenmann
TD-Delaunay graphs, where TD stands for triangular distance, is a variation of the classical Delaunay triangulations obtained from a specific convex distance function. Bonichon et.…
Encoding toroidal triangulations
Vincent Despré, Daniel Gonçalves, Benjamin Lévêque
Poulalhon and Schaeffer introduced an elegant method to linearly encode a planar triangulation optimally. The method is based on performing a special depth-first search algorithm o…
On the structure of Schnyder woods on orientable surfaces
Daniel Gonçalves, Kolja Knauer, Benjamin Lévêque
We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of higher genus. This is done in the language of angle labelings. Generalizing re…
Entropy compression method applied to graph colorings
Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou
Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović et al. on colorings, Esperet and Parreau developed…
Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations
Daniel Gonçalves, Benjamin Lévêque
A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to graphs embedded on…
The Maximum Clique Problem in Multiple Interval Graphs
Mathew C. Francis, Daniel Gonçalves, Pascal Ochem
Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of…
The Domination Number of Grids
Daniel Gonçalves, Alexandre Pinlou, Michael Rao +1
In this paper, we conclude the calculation of the domination number of all grid graphs. Indeed, we prove Chang's conjecture saying that for every , $γ(G_{…