Results 51 to 60 of about 4,621 (198)

A Polynomial-time Algorithm for Outerplanar Diameter Improvement

, 2014
The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$.
Cohen, Nathann, Gonçalves, Daniel, Kim, Eun Jung, Paul, Christophe, Sau, Ignasi, Thilikos, Dimitrios M., Weller, Mathias   +6 more
core   +3 more sources

Labeling Schemes for Bounded Degree Graphs [PDF]

, 2014
We investigate adjacency labeling schemes for graphs of bounded degree $\Delta = O(1)$. In particular, we present an optimal (up to an additive constant) $\log n + O(1)$ adjacency labeling scheme for bounded degree trees.
A. Korman, C. Gavoille, C. Gavoille, C. Nash-Williams, F.R.K. Chung, L. Esperet, N. Bonichon, N. Bonichon, S. Alstrup, S. Bhatt, S. Butler, Y. Wang   +11 more
core   +1 more source

Alpha Labeling of Amalgamated Cycles

Theory and Applications of Graphs, 2022
A graceful labeling of a bipartite graph is an \a-labeling if it has the property that the labels assigned to the vertices of one stable set of the graph are smaller than the labels assigned to the vertices of the other stable set.
Christian Barrientos
doaj   +1 more source

Nullspace Embeddings for Outerplanar Graphs [PDF]

, 2017
21 pages.
Lovász, L., Schrijver, A.
openaire   +4 more sources

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

On infinite outerplanar graphs [PDF]

Mathematica Bohemica, 1994
In this Note, we study infinite graphs with locally finite outerplane embeddings, given a characterization by forbidden ...
Boza Prieto, Luis, Diánez Martínez, Ana Rosa, Márquez Pérez, Alberto   +2 more
openaire   +4 more sources

Face Sizes and the Connectivity of the Dual

Journal of Graph Theory, Volume 110, Issue 4, Page 379-391, December 2025.
ABSTRACT For each c ≥ 1, we prove tight lower bounds on face sizes that must be present to allow 1‐ or 2‐cuts in simple duals of c‐connected maps. Using these bounds, we determine the smallest genus on which a c‐connected map can have a simple dual with a 2‐cut and give lower and some upper bounds for the smallest genus on which a c‐connected map can ...
Gunnar Brinkmann, Kenta Noguchi, Heidi Van den Camp   +2 more
wiley   +1 more source

Fuzzy Outerplanar Graphs and Its Applications

International Journal of Computational Intelligence Systems
The concept of a crisp graph is essential in the study of outerplanar graphs because outerplanar graphs are a unique type of planar graphs containing special characteristics. One of the core concepts of crisp graphs, the notion of a subgraph, is utilized
Deivanai Jaisankar, Sujatha Ramalingam, Nagarajan Deivanayagampillai, Tadesse Walelign   +3 more
doaj   +1 more source

A Universal Point Set for 2-Outerplanar Graphs

, 2015
A point set $S \subseteq \mathbb{R}^2$ is universal for a class $\cal G$ if every graph of ${\cal G}$ has a planar straight-line embedding on $S$. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the
C Binucci, H Fraysseix, M Kurowski, MJ Bannister, P Angelini, P Bose, P Gritzmann, R Fulek, S Cabello   +8 more
core   +1 more source

Monitoring maximal outerplanar graphs [PDF]

Electronic Notes in Discrete Mathematics, 2014
In this paper we define a new concept of monitoring the elements of triangulation graphs by faces. Furthermore, we analyze this, and other monitoring concepts (by vertices and by edges), from a combinatorial point of view, on maximal outerplanar graphs.
Hernández Peñalver, Gregorio, Martins, Ana Mafalda   +1 more
openaire   +3 more sources