Your search

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.

Given a convex polyhedron with n vertices and F faces, what is the fewest number of pieces, each of which unfolds to a simple polygon, into which it may be cut by slices along edges? Shephard's conjecture says that this number is always 1, but it's still open. The fewest nets problem asks to provide upper bounds for the number of pieces in terms of n and/or F. We improve the previous best known bound of F/2 by proving that every convex polyhedron can be unfolded into no more than 3F/8 non-overlapping nets. If the polyhedron is triangulated, the upper bound we obtain is 4F/11.

Abstract:- We provide lower and upper bounds for the domination numbers and the connected domination numbers for outerplanar graphs. We also provide a recursive algorithm that finds a connected domination set for an outerplanar graph. Finally, we show that for outerplanar graphs where all bounded faces are 3-cycles, the problem of determining the connected domination number is equivalent to an art gallery problem, which is known to be NP-hard. Key-Words:- dominating sets, star forests, outerplanar graphs, art gallery 1

In this paper we consider a variation of the Art Gallery Problem. A set of points script G sign in a polygon Pn is a connected guard set for Pn provided that is a guard set and the visibility graph of the set of guards script G sign in Pn is connected. We use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any polygon with n sides is ⌊(n - 2)/2⌋. This result was originally established by induction by Hernández-Peńalver [3]. From this result it easily follows that if the art gallery is orthogonal (each interior angle is 90° or 270°), then the minimum number of connected guards is n/2 - 2. © Springer-Verlag Berlin Heidelberg 2003.

In this paper we consider a variation of the Art Gallery Problem for orthogonal polygons. A set of points in a polygon Pn is a connected guard set for Pn provided that is a guard set and the visibility graph of the set of guards in Pn is connected. The polygon P n is orthogonal provided each interior angle is 90° or 270°. First we use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any orthogonal polygon with n sides is n/2-2. This result was originally established by induction by Hernández-Peñalver. Then we prove a new result for art galleries with holes: we show that n/2-h connected guards are always sufficient to watch an orthogonal art gallery with n walls and h holes. This result is sharp when n = 4h + 4. We also construct galleries that require at least n/2-h-1 connected guards, for all n and h. © Springer-Verlag 2003.

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).

We prove a new theorem for orthogonal art galleries in which the guards must guard one another in addition to guarding the polygonal gallery. A set of points G in a polygon Pn is a k-guarded guard set for Pn provided that (i) for every point x in Pn there exists a point w in G such that x is visible from w; and (ii) every point in G is visible from at least k other points in G: The polygon Pn is orthogonal provided each interior angle is 90° or 270°. We prove that for k ≥ 1 and n ≥ 6 every orthogonal polygon with n sides has a k-guarded guard set of cardinality (Formula Presented.) this bound is best possible. This result extends our recent theorem that treats the case k = 1. © Springer-Verlag Berlin Heidelberg 2001.

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.

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 unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target configuration. Our algorithms involve a total of O(n 2) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n 2) parallel steps [8,10,4] or do not respect the constraints mentioned above [1]. In fact, in the setting considered, our algorithms are optimal, in the sense that certain reconfigurations require Ω(n) parallel steps. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configurations. © 2009 Springer-Verlag.