Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometry and Generation of a New Graph Planarity Game
128
0
0.0
(
0
)
Added by
Andr\\'e van Renssen
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify quality criteria for puzzle instances, and describe a method to generate high-quality instances. We also report on experiments that show how well this generation process works.
rate research
Read More
In a emph{fan-planar drawing} of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every $n$-vertex fan-planar drawing has at most $5n-10$ edges, and that this bound is tight for $n geq 20$. We extend their result, both from the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrain
We obtain a complete classification of graph products of finite abelian groups whose Cayley graphs with respect to the standard presentations are planar.
In general, a graph modification problem is defined by a graph modification operation $boxtimes$ and a target graph property ${cal P}$. Typically, the modification operation $boxtimes$ may be vertex removal}, edge removal}, edge contraction}, or edge addition and the question is, given a graph $G$ and an integer $k$, whether it is possible to transform $G$ to a graph in ${cal P}$ after applying $k$ times the operation $boxtimes$ on $G$. This problem has been extensively studied for particilar instantiations of $boxtimes$ and ${cal P}$. In this paper we consider the general property ${cal P}_{{phi}}$ of being planar and, moreover, being a model of some First-Order Logic sentence ${phi}$ (an FOL-sentence). We call the corresponding meta-problem Graph $boxtimes$-Modification to Planarity and ${phi}$ and prove the following algorithmic meta-theorem: there exists a function $f:Bbb{N}^{2}toBbb{N}$ such that, for every $boxtimes$ and every FOL sentence ${phi}$, the Graph $boxtimes$-Modification to Planarity and ${phi}$ is solvable in $f(k,|{phi}|)cdot n^2$ time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifmans Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
The emph{segment number} of a planar graph is the smallest number of line segments whose union represents a crossing-free straight-line drawing of the given graph in the plane. The segment number is a measure for the visual complexity of a drawing; it has been studied extensively. In this paper, we study three variants of the segment number: for planar graphs, we consider crossing-free polyline drawings in 2D; for arbitrary graphs, we consider crossing-free straight-line drawings in 3D and straight-line drawings with crossings in 2D. We first construct an infinite family of planar graphs where the classical segment number is asymptotically twice as large as each of the new variants of the segment number. Then we establish the $existsmathbb{R}$-completeness (which implies the NP-hardness) of all variants. Finally, for cubic graphs, we prove lower and upper bounds on the new variants of the segment number, depending on the connectivity of the given graph.
Partial differential equations can be solved on general polygonal and polyhedral meshes, through Polytopal Element Methods (PEMs). Unfortunately, the relation between geometry and analysis is still unknown and subject to ongoing research in order to identify weaker shape-regularity criteria under which PEMs can reliably work. We propose PEMesh, a graphical framework to support the analysis of the relation between the geometric properties of polygonal meshes and the numerical performances of PEM solvers. PEMesh allows the design of polygonal meshes that increasingly stress some geometric properties, by exploiting any external PEM solver, and supports the study of the correlation between the performances of such a solver and geometric properties of the input mesh. Furthermore, it is highly modular, customisable, easy to use, and provides the possibility to export analysis results both as numerical values and graphical plots. PEMesh has a potential practical impact on ongoing and future research activities related to PEM methods, polygonal mesh generation and processing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
