ﻻ يوجد ملخص باللغة العربية
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $Ssubset mathbb{R}^2$ and an angle $0 < theta leq 2pi$, we define the continuous Yao graph $cY(theta)$ with vertex set $S$ and angle $theta$ as follows. For each $p,qin S$, we add an edge from $p$ to $q$ in $cY(theta)$ if there exists a cone with apex $p$ and aperture $theta$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(theta)$ for different values of $theta$. Using a new algebraic technique, we show that $cY(theta)$ is a spanner when $theta leq 2pi /3$. We believe that this technique may be of independent interest. We also show that $cY(pi)$ is not a spanner, and that $cY(theta)$ may be disconnected for $theta > pi$.
We study biplane graphs drawn on a finite planar point set $S$ in general position. This is the family of geometric graphs whose vertex set is $S$ and can be decomposed into two plane graphs. We show that two maximal biplane graphs---in the sense tha
In an $mathsf{L}$-embedding of a graph, each vertex is represented by an $mathsf{L}$-segment, and two segments intersect each other if and only if the corresponding vertices are adjacent in the graph. If the corner of each $mathsf{L}$-segment in an $
Let $S subset mathbb{R}^2$ be a set of $n$ sites, where each $s in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t in S$ if and only if $|st| leq
We introduce the family of $k$-gap-planar graphs for $k geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated
A classic theorem by Steinitz states that a graph G is realizable by a convex polyhedron if and only if G is 3-connected planar. Zonohedra are an important subclass of convex polyhedra having the property that the faces of a zonohedron are parallelog