8 papers · 1 filter
Boxicity and Threshold Dimension of Zero Divisor Graphs
Marco Caoduro, Meike Neuwohner
The zero divisor graph of a finite commutative ring has as vertices the non-zero zero divisors of , with an edge between two elements exactly when their product is ze…
A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs
Marco Caoduro, Will Evans, Tao Gaede
The boxicity of a graph is the minimum dimension that admits a representation of as the intersection graph of a family of axis-parallel boxes in . Computi…
On the Boxicity of Line Graphs and of Their Complements
Marco Caoduro, András Sebő
The boxicity of a graph is the smallest dimension allowing a representation of it as the intersection graph of a set of -dimensional axis-parallel boxes. We present a simple…
Characterizing unimodular laminar hypergraphs via forbidden subhypergraphs
Marco Caoduro, Meike Neuwohner, Joseph Paat
The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity…
Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs
Marco Caoduro, András Sebő
The boxicity of a graph is the smallest dimension allowing a representation of it as the intersection graph of a set of -dimensional axis-parallel boxes. We present a simple…
Independence number of intersection graphs of axis-parallel segments
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1
We prove that for any triangle-free intersection graph of axis-parallel segments in the plane, the independence number of this graph is at least . W…