Search

The angular resolution of a planar straight-line drawing of a graph is the smallest angle formed by two edges incident to the same vertex. Garg and Tamassia (ESA '94) constructed a family of planar graphs with maximum degree $d$ that have angular resolution $O((\log d)^{\frac{1}{2}}/d^{\frac{3}{2}})$ in any planar straight-line drawing. This upper bound has been the best known upper bound on angular resolution for a long time. In this paper, we improve this upper bound. For an arbitrarily small positive constant $\varepsilon$, we construct a family of planar graphs with maximum degree $d$ that have angular resolution $O((\log d)^\varepsilon/d^{\frac{3}{2}})$ in any planar straight-line drawing., Comment: 7 pages, 6 figures

A (Euclidean) greedy drawing of a graph is a drawing in which, for any two vertices $s,t$ ($s \neq t$), there is a neighbor vertex of $s$ that is closer to $t$ than to $s$ in the Euclidean distance. Greedy drawings are important in the context of message routing in networks, and graph classes that admit greedy drawings have been actively studied. N\"{o}llenburg and Prutkin (Discrete Comput. Geom., 58(3), pp.543-579, 2017) gave a characterization of greedy-drawable trees in terms of an inequality system that contains a non-linear equation. Using the characterization, they gave a linear-time recognition algorithm for greedy-drawable trees of maximum degree $\leq 4$. However, a combinatorial characterization of greedy-drawable trees of maximum degree 5 was left open. In this paper, we give a combinatorial characterization of greedy-drawable trees of maximum degree $5$, which leads to a complete combinatorial characterization of greedy-drawable trees. Furthermore, we give a characterization of greedy-drawable pseudo-trees. It turns out that greedy-drawable pseudo-trees admit a simpler characterization than greedy-drawable trees., Comment: 16 pages, 17 fugures

The Folkman-Lawrence topological representation theorem, which states that every (loop-free) oriented matroid of rank $r$ can be represented as a pseudosphere arrangement on the $(r-1)$-dimensional sphere $S^{r-1}$, is one of the most outstanding results in oriented matroid theory. In this paper, we provide a lower-dimensional version of the topological representation theorem for uniform matroid polytopes of rank $4$. We introduce $2$-weak configurations of points and pseudocircles ($2$-weak PPC configurations) on $S^2$ and prove that every uniform matroid polytope of rank $4$ can be represented by a $2$-weak PPC configuration. As an application, we provide a proof of Las Vergnas conjecture on simplicial topes for the case of uniform matroid polytopes of rank $4$., Comment: 15 pages

Many combinatorial properties of a point set in the plane are determined by the set of possible partitions of the point set by a line. Their essential combinatorial properties are well captured by the axioms of oriented matroids. In fact, Goodman and Pollack (Journal of Combinatorial Theory, Series A, Volume 37, pp. 257-293, 1984) proved that the axioms of oriented matroids of rank $3$ completely characterize the sets of possible partitions arising from a natural topological generalization of configurations of points and lines. In this paper, we introduce a new class of oriented matroids, called degree-$k$ oriented matroids, which captures essential combinatorial properties of the possible partitions of point sets in the plane by the graphs of polynomial functions of degree $k$. We prove that the axiom of degree-$k$ oriented matroids completely characterizes the sets of possible partitions arising from a natural topological generalization of configurations formed by points and the graphs of polynomial functions degree $k$. It turns out that the axiom of degree-$k$ oriented matroids coincides with the axiom of ($k+2$)-signotopes, which was introduced by Felsner and Weil (Discrete Applied Mathematics, Volume 109, pp. 67-94, 2001) in a completely different context. Our result gives a two-dimensional geometric interpretation for ($k+2$)-signotopes and also for single element extensions of cyclic hyperplane arrangements in $\mathbb{R}^{n-k-3}$., Comment: 15 pages