Your search
Results 7 resources
-
A conjecture by Albertson states that if χ(G) ≥ n then cr(G) ≥ cr(Kn), where χ(G) is the chromatic number of G and cr(G) is the crossing number of G. This conjecture is true for positive integers n ≤ 16, but it is still open for n ≥ 17. In this paper we consider the statements corresponding to this conjecture where the crossing number of G is replaced with the skewness µ(G) (the minimum number of edges whose removal makes G planar), the genus γ(G) (the minimum genus of the orientable surface on which G is embeddable), and the thickness θ(G) (the minimum number of planar subgraphs of G whose union is G.) We show that the corresponding statements are true for all positive integers n when cr(G) is replaced with µ(G) or γ(G). We also show that the corresponding statement is true for infinitely many values of n, but not for all n, when cr(G) is replaced with θ(G).
-
We consider variations of the original art gallery problem where the domain is a polyomino, a polycube, or a polyhypercube. An m-polyomino is the connected union of m unit squares called pixels, an m-polycube is the connected union of m unit cubes called voxels, and an m-polyhypercube is the connected union of m unit hypercubes in a d dimensional Euclidean space. In this paper we generalize and unify the known results about guarding polyominoes and polycubes and obtain simpler proofs. We also obtain new art gallery theorems for guarding polyhypercubes. © 2015 Elsevier B.V.
-
Hoffmann and Kriegel showed that an orthogonal gallery with n vertices and an unspecified number of holes can be protected by at most n/3 vertex guards. We improve this bound to (17n − 8)/52.
-
Let P be an orthogonal polygon with n vertices, and let V⁎ and E⁎ be specified sets of vertices and edges of P. We prove that P has a guard set of cardinality at most ⌊(n+3|V⁎|+2|E⁎|)/4⌋ that includes each vertex in V⁎ and at least one point of each edge in E⁎. Our bound is sharp and reduces to the orthogonal art gallery theorem of Kahn, Klawe and Kleitman when V⁎ and E⁎ are empty. © 2016 Elsevier B.V.
-
We extend and unify most known results about guarding orthogonal polygons by introducing the same-sign diagonal graphs of a convex quadrangulation and applying results about vertex covers for graphs. Our approach also yields new theorems and often guarantees two disjoint vertex guard sets of relatively small cardinality. For instance, an orthogonal polygon on n vertices has two disjoint vertex guard sets of cardinality at most (Formula presented.). We give new proofs of Aggarwal’s one-hole theorem and the orthogonal fortress theorem. We prove that an orthogonal polygon with n vertices and any number of holes can be protected by at most (Formula presented.) vertex guards, improving the best known bound of (Formula presented.). Also, an orthogonal polygon with n vertices and h holes can be protected by (Formula presented.) guarded guards, which is best possible when (Formula presented.). Moreover, for orthogonal fortresses with n vertices, (Formula presented.) guarded guards are always sufficient and sometimes necessary. © 2016, Springer Science+Business Media New York (outside the USA).
-
In this paper, we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 × 2 × 2 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration. Our algorithms involve a total of O(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication. © 2011 Cambridge University Press.
Explore
Resource type
- Journal Article (7)
Publication year
Resource language
- English (5)