Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAxis-Aligned Square Contact Representations
61
0
0.0
(
0
)
Added by
Andrew Nathenson
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Andrew Nathenson
Ask ChatGPT about the research
No Arabic abstract
We introduce a new class $mathcal{G}$ of bipartite plane graphs and prove that each graph in $mathcal{G}$ admits a proper square contact representation. A contact between two squares is emph{proper} if they intersect in a line segment of positive length. The class $mathcal{G}$ is the family of quadrangulations obtained from the 4-cycle $C_4$ by successively inserting a single vertex or a 4-cycle of vertices into a face. For every graph $Gin mathcal{G}$, we construct a proper square contact representation. The key parameter of the recursive construction is the aspect ratio of the rectangle bounded by the four outer squares. We show that this aspect ratio may continuously vary in an interval $I_G$. The interval $I_G$ cannot be replaced by a fixed aspect ratio, however, as we show, the feasible interval $I_G$ may be an arbitrarily small neighborhood of any positive real.
rate research
Read More
Weak unit disk contact graphs are graphs that admit representing nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. In this work we focus on graphs without embedding, i.e., the neighbor order can be chosen arbitrarily. We give a linear time algorithm to recognize whether a caterpillar, a graph where every node is adjacent to or on a central path, allows a weak unit disk contact representation. On the other hand, we show that it is NP-hard to decide whether a tree allows such a representation.
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. We provide a gadget-based reduction to show that recognizing embedded caterpillars that admit a weak unit disk contact representation is NP-hard.
In the field of topology optimization, the homogenization approach has been revived as an important alternative to the established, density-based methods because it can represent the microstructural design at a much finer length-scale than the computational grid. The optimal microstructure for a single load case is an orthogonal rank-3 laminate. A rank-3 laminate can be described in terms of frame fields, which are also an important tool for mesh generation in both 2D and 3D. We propose a method for generating multi-laminar structures from frame fields. Rather than relying on integrative approaches that find a parametrization based on the frame field, we find stream surfaces, represented as point clouds aligned with frame vectors, and we solve an optimization problem to find well-spaced collections of such stream surfaces. The stream surface tracing is unaffected by the presence of singularities outside the region of interest. Neither stream surface tracing nor selecting well-spaced surface rely on combed frame fields. In addition to stream surface tracing and selection, we provide two methods for generating structures from stream surface collections. One of these methods produces volumetric solids by summing basis functions associated with each point of the stream surface collection. The other method reinterprets point sampled stream surfaces as a spatial twist continuum and produces a hexahedralization by dualizing a graph representing the structure. We demonstrate our methods on several frame fields produced using the homogenization approach for topology optimization, boundary-aligned, algebraic frame fields, and frame fields computed from closed-form expressions.
We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that point to each other inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with small faces has a turn-regular orthogonal representation without bends.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
