Results 41 to 50 of about 17,567 (164)
L(2, 1)-Labelings of Some Families of Oriented Planar Graphs
Discussiones Mathematicae Graph Theory, 2014 In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.
Sen Sagnik
doaj +1 more source
NP-Completeness Results for Minimum Planar Spanners [PDF]
Discrete Mathematics & Theoretical Computer Science, 1998 For any fixed parameter t greater or equal to 1, a t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G.
Ulrik Brandes, Dagmar Handke
doaj +2 more sources
Negative results on acyclic improper colorings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number $k$ is at most $k2^{k-1}$. We prove that this bound is tight for $k \geq 3$.
Pascal Ochem
doaj +1 more source
Journal of Computational Geometry, 2022 Morphing geometric graphs is a classical problem in graph theory and computational geometry with seminal results established by Cairns in 1944 [Amer. Math. Monthly, 51] and by Thomassen in 1983 [J. of Comb. Theor., Series B, 34].
Patrizio Angelini +3 more
doaj +1 more source
On RAC drawings of 1-planar graphs
Theoretical Computer Science, 2017 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bekos, Michael A. +4 more
openaire +2 more sources
1-planarity of complete multipartite graphs
Discrete Applied Mathematics, 2012 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Július Czap, Dávid Hudák
openaire +2 more sources
Stack and Queue Layouts via Layered Separators
Journal of Graph Algorithms and Applications, 2018 It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not
Vida Dujmović, Fabrizio Frati
doaj +1 more source
About Structure of Graph Obstructions for Klein Surface with 9 Vertices
Кібернетика та комп'ютерні технології, 2020 The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of (-transformations of the graphs.
V.I. Petrenjuk, D.A. Petrenjuk
doaj +1 more source
Improvements on the density of maximal 1‐planar graphs [PDF]
Journal of Graph Theory, 2017 AbstractA graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al.
János Barát, Géza Tóth 0001
openaire +4 more sources