Navigating clustered graphs using force-directed methods.
Near-homogeneous spherical Latin bitrades
A planar Eulerian triangulation is a simple plane graph in which each face is a triangle and each vertex has even degree. Such objects are known to be equivalent to spherical Latin bitrades. (A Latin bitrade describes the difference between two Latin squares of the same order.) We give a classification in the near-regular case when each vertex is of degree or (which we call a near-homogeneous spherical Latin bitrade, or NHSLB). The classification demonstrates that any NHSLB is equal to two graphs...
Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles
Let be a simple graph and denote the set of edges incident with a vertex . A neighbor sum distinguishing (NSD) total coloring of is a proper total coloring of such that for each edge . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree admits an NSD total -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with but without -cycles by applying the Combinatorial Nullstellensatz.
Neighborly Maps with Few Vertices.
New infinite families of almost-planar crossing-critical graphs.
New lower bounds for orthogonal drawings.
New upper bounds for the crossing number of on the Klein bottle
Non-orientable biembeddings of Steiner triple systems of order 15.
Nonorientable Genus of Nearly Complete Bipartite Graphs.
Note on Induced Subgraphs of the Unit Distance Graph En.
Note on the weight of paths in plane triangulations of minimum degree 4 and 5
The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.
O jednom zobecnění vnějškově rovinných grafů
Octonion multiplication and Heawood’s map
In this note, the octonion multiplication table is recovered from a regular tesselation of the equilateral two timensional torus by seven hexagons, also known as Heawood’s map.
On 2-cell embeddings of graphs with minimum numbers of regions
On 2-cell imbeddings of complete n-partite graphs
On 3-simplicial vertices in planar graphs
A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.
On a certain class of polytopes associated with independence systems.
On a certain distance between isomorphism classes of graphs
On a matching distance between rooted phylogenetic trees
The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values...
On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true...