|
|||||
Computational Geometry
[PDF]
[PDF]
- EDWARD LEE, University of Waterloo
Recognizing Circle Graphs [PDF]
-
A circle graph is the intersection graph of chords on a circle.
There is a correspondence between bipartite
circle graphs and planar graphs, and hence every characterization for the class
of circle graphs gives a characterization for the class of planar graphs.
Given a graph, Naji describes a system of linear equations whose solvability determines whether or not the graph is a circle graph. We will sketch a new proof of this beautiful theorem which is considerably simpler than the existing proofs due to Naji, Gasse, and Traldi.
This is joint work with Jim Geelen.
- SHIKHA MAHAJAN, University of Waterloo
A Faster Algorithm for Recognizing Edge-Weighted Interval Graphs [PDF]
-
We investigate an edge-weighted version of interval graphs. A graph with weights on its edges is an edge-weighted interval graph if we can assign intervals to the vertices so that the weight of an edge $(u,v)$ is equal to the length of the intersection of the intervals assigned to $u$ and $v$. In 2012, K\"{o}bler, Kuhnert, and Watanabe gave an algorithm to recognize such graphs in time $O(m \cdot n)$, where $m$ and $n$ are the number of edges and vertices, respectively, of the given graph. We improve the runtime of this algorithm to $O(m \cdot \log{n})$ using $PQ$ trees. \newline \newline
Joint work with Anna Lubiw.
- JAKUB SOSNOVEC, University of Warwick
Squarability of Rectangle Arrangements [PDF]
-
We study when an arrangement of axis-aligned rectangles can be transformed into an arrangement of axis-aligned squares in $\mathbb{R}^2$ while preserving its structure. We found a counterexample to the conjecture of J. Klawitter, M. N\"{o}llenburg and T. Ueckerdt whether all arrangements without crossing and side-piercing can be squared. Our counterexample also works in a more general case when we only need to preserve the intersection graph and we forbid sidepiercing between squares. We also show counterexamples for transforming box arrangements into combinatorially equivalent hypercube arrangements. Finally, we introduce a linear program deciding whether an arrangement of rectangles can be squared in a more restrictive version where the order of all sides is preserved. Joint work with Mat\v{e}j Kone\v{c}n\'{y}, Stanislav Ku\v{c}era, Michal Opler, \v{S}t\v{e}p\'{a}n \v{S}imsa and Martin T\"{o}pfer.
