اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAxis-Aligned Square Contact Representations
61
0
0.0
(
0
)
تأليف
Andrew Nathenson
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 sho
w 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 comput
ational 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 i
n 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
