Computer Science Department, University of California, Irvine,
<EMAIL_ADDRESS>in part by NSF grants CCF-1618301 and
CCF-1616248. David Eppstein [500]Theory of computation Computational geometry
[500]Human-centered computing Graph drawings Gill Barequet and Yusu Wang 2
35th International Symposium on Computational Geometry (SoCG 2019) SoCG 2019
SoCG 2019 June 18–21, 2019 Portland, United States socg-logo 129 32

# Cubic Planar Graphs That Cannot Be Drawn On Few Lines

David Eppstein

###### Abstract

For every integer $\ell$, we construct a cubic 3-vertex-connected planar
bipartite graph $G$ with $O(\ell^{3})$ vertices such that there is no planar
straight-line drawing of $G$ whose vertices all lie on $\ell$ lines. This
strengthens previous results on graphs that cannot be drawn on few lines,
which constructed significantly larger maximal planar graphs. We also find
apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on
a bounded number of lines.

###### keywords:

graph drawing, universal point sets, collinearity

##  1 Introduction

A number of works in graph drawing and network visualization have considered
drawing graphs with line segments as edges and with the vertices placed on few
lines, or on a minimal number of lines. Even very strong constraints, such as
restricting the vertices of a drawing to only two lines, allow many graphs to
be drawn [16]: every _weakly leveled_ graph drawing (a planar drawing on any
number of parallel lines with every edge connecting two vertices on the same
or adjacent lines) can be converted into a drawing on two crossing lines that
spirals around the crossing. This conversion allows, for instance, all trees,
all outerplanar graphs, all Halin graphs, all squaregraphs (graphs in which
all bounded faces have exactly four sides and all vertices not on the
unbounded face have at least four neighbors) and all grid graphs (fig:2line-
grid) to be drawn on two lines [2, 15, 1].

Figure 1: Spiraling around the central crossing allows every weakly leveled
drawing (in this case, a drawing of a grid graph) to be converted to a drawing
with all vertices on two lines.

Additional past results in this area include:

  * •

Fixed-parameter tractable algorithms for drawing planar graphs without
crossings with all vertices on $\ell$ parallel lines, based on the fact that a
graph with such a drawing must have pathwidth $O(\ell)$ [8].

  * •

NP-hardness of crossing minimization for graphs drawn with vertices on two
parallel lines (with a fixed assignment of vertices to lines but variable
placement of each vertex along each line) and of finding large crossing-free
subgraphs [12, 13].

  * •

NP-hardness of recognizing the graphs that can be drawn without crossing with
all vertices on three parallel but non-coplanar lines in three-dimensional
space, or on three rays in the plane with a common apex and bounding three
wedges with angles less than $\pi$ [2]. More generally, the number of parallel
three-dimensional lines (in sufficiently general position) needed for a
crossing-free drawing of a graph is the _track number_ of the graph [10, 11].
It is closely related to the volume of three-dimensional grid drawings, and
can be bounded by the pathwidth of the graph [9].

  * •

$\exists\mathbb{R}$-completeness and fixed-parameter tractability of deciding
whether a given graph can be drawn without crossing with all edges on $\ell$
lines (not required to be parallel) in two or three dimensions [4].

  * •

Implementation of a tester for drawing graphs without crossings on two lines
using integer linear programming and SAT solvers, and an examination of the
subclasses of planar graphs that can be drawn without crossings with all
vertices on two lines [16].

  * •

The existence of families of planar graphs that cannot be drawn without
crossings on any fixed number of lines, no matter how the lines are arranged
in the plane [19, 5, 14].

In this paper we strengthen the final result of this listing, the existence of
families of planar graphs that cannot be drawn on any fixed number of lines,
in two ways.

First, we greatly improve the size bounds for these difficult-to-draw graphs.
The previous bounds of Ravsky, Chaplick, et al. [19, 5] are based on the
observation that, in a maximal planar graph, a line through $q$ vertices
implies the existence of a path in the dual graph of length $\Omega(q)$.
However, there exist $n$-vertex maximal planar graphs for which the longest
dual path has length $O(n^{c})$ for some constant $c<1$ called the _shortness
exponent_. In these graphs, at most $O(n^{c})$ vertices can lie on one line,
so the number of lines needed to cover the vertices of any drawing of such a
graph is $\Omega(n^{1-c})$. Based on this reasoning, they showed the existence
of $n$-vertex graphs requiring $O(n^{0.01})$ lines to cover the vertices of
any drawing. Inverting this relationship, graphs that cannot be drawn on
$\ell$ lines can have a number of vertices that is only polynomial in $\ell$,
but that polynomial is roughly $\ell^{100}$. Alternatively, it can be proven
by a straightforward induction that a special class of maximal planar graphs,
the planar 3-trees, cannot be drawn on a constant number of lines, but the
proof only shows that the required number of lines for these graphs is at
least logarithmic [14]. Inverting this relationship, the graphs of this type
that cannot be drawn on $\ell$ lines have size exponential in $\ell$. In this
paper, we prove polynomial bounds with a much smaller exponent than $100$.

Figure 2: A cubic planar graph that cannot be drawn on two lines, giving a
counterexample to a conjecture of Firman et al. [16]. Its inability to be
drawn on two lines has been verified computationally by Firman et al.

Second, we show that the property of requiring many lines extends to a broader
class of graphs. Both classes of counterexamples discussed above involve
maximal planar graphs, graphs in which every face of the embedding is a
triangle. Maximality seems a necessary part of the proofs based on the
shortness exponent, as the connection between numbers of vertices on a single
line and lengths of dual paths does not necessarily hold for other classes of
planar graphs. In contrast, based on computational experiments, Firman et al.
[16] conjectured that cubic (that is, 3-regular) planar graphs can always be
drawn without crossings on only two lines. The cubic graphs are distinct from
the known examples of graphs that require their vertices to lie on many lines,
as a maximal planar graph larger than $K_{4}$ cannot be cubic. Their
conjecture inspired the present work, and a counterexample to it found by the
author (fig:2line-counterexample) led to our main results. In this work, we
provide examples of graphs that require many lines but are cubic, providing
stronger counterexamples to the conjecture of Firman et al. Moreover these
graphs do not contain any triangles, showing that the presence of triangles is
not a necessary component of graphs that require many lines.

More specifically, we prove:

######  Theorem 1.1.

For every $\ell$ there exists a graph $G_{\ell}$ that is cubic, 3-vertex-
connected, planar, and bipartite, with $O(\ell^{3})$ vertices, such that every
straight-line planar drawing of $G_{\ell}$ requires more than $\ell$ lines to
cover all vertices of the drawing.

Additionally, we can construct $G_{\ell}$ in such a way that it is drawable
with its vertices on $O(\ell)$ lines, or such that it has bounded pathwidth.
In particular, this proves that the relation between pathwidth and number of
lines proven by Dujmović et al. [8] is not bidirectional. Every graph that can
be drawn without crossings on a given number of parallel lines has pathwidth
bounded linearly in the number of lines, but the number of lines needed to
draw a planar graph cannot be bounded by a function of its pathwidth,
regardless of whether we constrain the lines to be parallel.

Using similar methods, we also prove:

######  Theorem 1.2.

For every $\ell$ there exists a subcubic series-parallel graph that cannot be
drawn with its vertices on $\ell$ lines, and an apex-tree (a graph formed by
adding one vertex to a tree) that cannot be drawn with its vertices on $\ell$
lines.

thm:treelike stands in contrast to the fact that all trees and all outerplanar
graphs can be drawn on only two crossed lines. In thm:treelike, both the
series-parallel graph and apex-tree can be made to be bipartite, and the apex-
tree can be made subcubic at all tree vertices.

These results lower the treewidth of the known graphs that cannot be drawn on
a constant number of lines from three [14] to two, and they show that adding
one vertex to a graph can change the number of lines needed to draw it from
two to any larger number. The apex-tree graphs are also central to recent
research characterizing the minor-closed families of bounded layered pathwidth
[7]. However, for thm:treelike we do not have a polynomial size bound on the
graphs that we construct; instead, they are exponential in size. At least in
the case of apex-trees, this exponential size blowup is necessary, as we
finally prove:

######  Theorem 1.3.

Every apex-tree with $n$ vertices has a planar embedding that can be drawn
with its vertices on $O(\log n)$ parallel lines.

##  2 Counterexamples of cubic size

Figure 3: The overall construction plan of our graph: $O(\ell^{2})$ copies of
a subgraph formed from $O(\ell)$ nested hexagons.

###  2.1 Overview

The overall strategy of our construction for graphs of size $O(\ell^{3})$ that
cannot be drawn on $\ell$ lines is illustrated in fig:spiderwebs. As can be
seen in the figure, the graph consists of a number of subunits, each formed by
a set of nested hexagons, connected to each other by triples of edges. These
subunits resemble the _nested triangles graph_ frequently used as a
counterexample in graph drawing [6, 17], but are based on hexagons rather than
triangles.

The figure shows faces of three types: triples of quadrilaterals at the center
of each set of nested hexagons, non-convex L-shaped hexagonal faces between
pairs of hexagons in each set of nested hexagons, and Y-shaped dodecagonal
faces between triples of subunits. Because the graph is planar and each
bounded face has an even number of sides, the graph is also bipartite. It is
straightforward to add a small number of additional vertices surrounding the
sets of nested hexagons (as shown) to complete the graph to one that is cubic,
3-vertex-connected, and still bipartite. Because it is 3-vertex-connected, it
has a unique planar embedding, the one shown, up to the choice of which face
of the embedding is the outer face. With at most one exception (the subunit
that includes the outer face), all subunits must be drawn as shown in the
figure (topologically but not geometrically), within disjoint hexagonal
regions of the plane.

The drawing also shows that each subunit can be drawn using only three lines.
Indeed, the number of lines needed to cover all of the vertices in
fig:spiderwebs (and in similar figures with more subunits) is proportional
only to the square root of the number of subunits. Nevertheless, we shall show
that, if there are enough subunits relative to the number of lines, then at
least one of the subunits will be difficult to draw on few lines. More
specifically, for a given parameter $\ell$ (a number of lines that should be
too small to cover all vertices of the drawing) we will choose the number of
subunits to be at least $\tbinom{\ell}{2}+2$, two more than the largest
possible number of crossing points that $\ell$ lines can have. In this way,
there will be at least one subunit that does not include the outer face of the
embedding, and does not surround any crossing points of the lines.

We will show that, for subunits formed from a sufficiently large number of
nested hexagons (linear in $\ell$), it is not possible to draw the subunit on
$\ell$ lines without surrounding any crossing points. Because, nevertheless,
one of the subunits must fail to surround any crossing points, it cannot be
drawn on $\ell$ lines. It follows that the whole graph also cannot be drawn on
$\ell$ lines.

###  2.2 Nested polygons with no surrounded crossings

To formalize the subunits of the drawing of fig:spiderwebs, we define a
_$(p,r)$ -nest_, for positive integers $p$ and $r$, to be a collection of $r$
disjoint simple $p$-gons (not necessarily convex), together with one
additional point (the _egg_), such that each $p$-gon contains the egg. Because
the $p$-gons are disjoint and all contain the egg, it is necessarily the case
(by the Jordan curve theorem) that each two of the $p$-gons are nested, one
inside the other. Then the subunits of fig:spiderwebs form a $(6,r)$-nest, for
some $r$, together with some additional graph edges between consecutive cycles
that force the cycles to be nested within each other but play no additional
role in our analysis.

In fig:spiderwebs, each $(6,r)$-nest is drawn with all hexagon vertices on
three lines that cross at the egg of the nest. More generally, whenever $p$ is
even, a $(p,r)$-nest can be drawn on only two crossing lines, with the egg at
the crossing point; when $p$ is odd, three lines suffice. However, in all of
these drawings, a crossing point of the lines is contained within at least one
polygon of the nest. We will show that, when this does not happen, nests
require $\Omega(r/p)$ lines to cover all of their points.

######  Lemma 2.1.

Let $p$ be a positive integer, let $P$ be a simple $p$-gon, and let $L$ be a
line. Then $L$ intersects the interior of $P$ in at most $\lfloor p/2\rfloor$
open line segments.

######  Proof 2.2.

Each line segment begins and ends at points where $L$ intersects $P$ either at
a vertex or at an interior point of one of the sides of $P$. If the segment
endpoint is at a crossing of $L$ with an interior point of a side of $P$, then
that point is the endpoint of only one segment of $L$, and is the only point
of intersection of $L$ with that side. If the segment endpoint is a vertex of
$P$, then it may be the endpoint of of two segments of $L$, but in that case
it is the only point of intersection of $L$ with both sides incident to the
vertex. So in either case each endpoint of a segment of $L$ uses up at least
one side of $P$. As $P$ has $p$ sides, the number of segments is at most
$\lfloor p/2\rfloor$.

######  Corollary 2.3.

Let $\mathcal{A}$ be an arrangement of $\ell$ lines, and let $P$ be a simple
$p$-gon whose interior is disjoint from the crossings of $\mathcal{A}$. Then
the lines of $\mathcal{A}$ intersect the interior of $P$ in at most
$\ell\cdot\lfloor p/2\rfloor$ open line segments.

######  Lemma 2.4.

Let $\mathcal{A}$ be an arrangement of lines and $P$ be a simple polygon that
does not contain any crossing point of $\mathcal{A}$. Then the lines of
$\mathcal{A}$ partition the interior of $P$ into regions in such a way that
the graph of regions and their adjacencies forms a tree.

######  Proof 2.5.

To show that the graph of regions and adjacencies is connected, consider any
two regions $R_{i}$ and $R_{j}$, and choose a curve $C$ within the interior of
$P$ connecting any point in $R_{i}$ to any point in $R_{j}$. Then the sequence
of regions crossed by $C$ forms a walk in the region adjacency graph
connecting $R_{i}$ to $R_{j}$.

To show that the graph of regions and adjacencies has no simple cycle, assume
for a contradiction that there is such a cycle. Then by choosing a
representative point within each region of the cycle, and connecting these
points by curves that pass between adjacent regions without crossing any other
regions, we can form a simple closed curve $C$ in the plane that crosses the
lines of $\mathcal{A}$ in exactly the order given by the cycle. By the Jordan
curve theorem, each line that crosses into the interior of $C$ must cross out
of $C$ at another point. Two crossings of $C$ by the same line cannot be
adjacent in the cyclic order of crossings, for then the graph cycle
corresponding to $C$ would not be simple. Therefore, $C$ is crossed by at
least two lines, in alternating order. But this can happen only when $C$
contains the crossing point of these lines, an impossibility as $C$ is
entirely contained in $P$ which we assumed to enclose no crossings. This
contradiction shows that a simple cycle does not exist.

As a connected graph with no simple cycles, the graph of regions and
adjacencies must be a tree.

######  Lemma 2.6.

Let $\mathcal{A}$ be an arrangement of lines and $P$ be a simple polygon that
does not contain any crossing point of $\mathcal{A}$. Let $\mathcal{S}$ be the
system of disjoint open line segments formed by intersecting the lines of
$\mathcal{A}$ with the interior of $P$, and let $Q$ be another simple polygon,
disjoint from $P$, such that each vertex of $Q$ lies on a segment of
$\mathcal{S}$. Then at least two segments of $\mathcal{S}$ are disjoint from
the interior of $Q$.

######  Proof 2.7.

Because the graph of regions and adjacencies formed in $P$ by $\mathcal{A}$ is
a tree (lem:region-tree), it has at least two leaves. Let $s$ be either of the
two segments of $\mathcal{S}$ separating one of these leaf regions from the
rest of $P$. Then no edge of $Q$ can enter the interior of this leaf region,
because there is no other segment available to be the endpoint of this edge.
Therefore, $Q$ remains entirely on one side of $s$, and $s$ is disjoint from
the interior of $Q$. As there were at least two choices for $s$, there are at
least two segments of $\mathcal{S}$ that are disjoint from the interior of
$Q$.

Putting these observations together, we have:

######  Lemma 2.8.

Let $\mathcal{A}$ be an arrangement of $\ell$ lines, let $p$ and $r$ be
positive integers, and suppose that $2(r-1)>\ell\cdot\lfloor p/2\rfloor$. Then
it is not possible to draw a $(p,r)$-nest in such a way that the polygon
vertices of the nest and its egg all lie on lines of $\mathcal{A}$.

######  Proof 2.9.

Suppose for a contradiction that we have drawn a $(p,r)$-nest with all points
on lines of $\mathcal{A}$. Let $\mathcal{S}$ be the system of disjoint open
line segments formed by intersecting the lines of $\mathcal{A}$ with the outer
polygon of the nest. Then $|\mathcal{S}|\leq\ell\cdot\lfloor p/2\rfloor$ by
cor:few-segs, and each of the $r-1$ remaining polygons of the nest use up at
least two of the segments of $\mathcal{S}$ by lem:use-two. Therefore, if
$2(r-1)>\ell\cdot\lfloor p/2\rfloor$ (as we supposed in the statement of the
lemma), there will be no segments remaining for the egg to lie on. Therefore,
a drawing meeting these conditions is impossible.

Figure 4: An arrangement of $\ell$ lines can support $\lfloor
3(\ell-1)/2-1\rfloor$ nested hexagons surrounding a central point, with the
point and the hexagon vertices all on the lines, and all arrangement crossings
exterior to all hexagons.

In the particular case of a $(6,r)$-nest (as used in fig:spiderwebs),
lem:deep-nest states that a drawing that does not contain an arrangement
crossing cannot exist for $r\geq 3\ell/2+2$. This is close to tight:
fig:hexnest shows how to draw a $(6,r)$-nest with all polygon vertices and the
egg on $\ell$ lines, for $r=3\ell/2-O(1)$.

###  2.3 The main result

######  Proof 2.10 (Proof of thm:cubic).

We wish to show the existence of a planar cubic bipartite graph that cannot be
drawn on $\ell$ lines, for a given parameter $\ell$. Consider a cubic
bipartite 3-vertex-connected planar graph formed, as in fig:spiderwebs, by at
least $\tbinom{l}{2}+2$ subunits, each of which must be drawn as a
$(6,r)$-nest, for $r=\lceil 3\ell/2\rceil+2$. Because there are $O(\ell^{2})$
subunits, each of size $O(\ell)$, and $O(\ell)$ vertices surrounding the
subunits, the total size of the resulting graph is $O(\ell^{3})$.

To argue that the resulting graph cannot be drawn on $\ell$ lines, we consider
an arbitrary arrangement $\mathcal{A}$ with $\ell$ lines, and prove that the
graph cannot be drawn with all of its vertices on $\mathcal{A}$. Among the
graph’s $\tbinom{l}{2}+2$ subunits, one subunit (the one from which the outer
face was chosen) can surround all the others, but the rest must be drawn in
disjoint regions of the plane. Because there are more remaining subunits than
the number of crossing points of $\mathcal{A}$ (which is at most
$\tbinom{\ell}{2}$), at least one subunit must be drawn in such a way that it
does not contain any of the crossing points of $\mathcal{A}$. However, by
lem:deep-nest, this is impossible.

Figure 5: Zigzag pattern of subunits (shown schematically as hexagons) used to
construct a graph of pathwidth $O(1)$ that cannot be drawn on few lines.

When the subunits of the graph are arranged as in fig:spiderwebs, into a
compact hexagonal grid in the plane, then (as the figure shows) the vertices
of the whole graph can be covered by $O(\ell)$ lines, even though we have
proved that there is no cover by $\ell$ lines. Alternatively, it is possible
to arrange the subunits into a linear zig-zag pattern (fig:zigzag), preserving
the 3-vertex-connectedness of the resulting graph and still requiring only
$O(\ell^{2})$ vertices to surround the subunits. When the subunits are
arranged in this way, the resulting graph might require a larger number of
lines to cover its vertices (i.e., we do not have tight bounds on the number
of lines needed for a graph of this form), but it has pathwidth $O(1)$.

##  3 Series-parallel graphs

A _two-terminal series-parallel graph_ (series-parallel graph, for short) is a
graph with two distinct designated _terminal_ vertices $s$ and $t$ formed
recursively from smaller graphs of the same type (starting from a single edge)
by two operations:

  * •

Series composition: given two series-parallel graphs $G_{1}$ and $G_{2}$ with
terminals $s_{1}$, $t_{1}$, $s_{2}$, and $t_{2}$, form their disjoint union,
and then merge vertices $s_{2}$ and $t_{1}$ into a single vertex. Let the
terminals of the resulting merged graph be the unmerged terminals of the given
graphs, $s_{1}$ and $t_{2}$. Series composition forms an associative binary
operation on these graphs (if we perform series compositions on a sequence of
more than two graphs, the order in which we perform the compositions does not
affect the result).

  * •

Parallel composition: given two series-parallel graphs $G_{1}$ and $G_{2}$
with terminals $s_{1}$, $t_{1}$, $s_{2}$, and $t_{2}$, form their disjoint
union, merge vertices $s_{1}$ and $s_{2}$ into a single vertex, and similarly
merge $t_{1}$ and $t_{2}$ into a single vertex. Let the terminals of the
resulting merged graph be the resulting merged vertices. Parallel composition
forms an associative and commutative binary operation on these graphs (if we
perform series compositions on a set of more than two graphs, neither the
order of the two graphs in each composition nor the order in which we perform
the compositions affects the result).

These graphs have treewidth two, and every graph of treewidth two is a
subgraph of a series-parallel graph. They are automatically planar, and they
include every outerplanar graph.

Figure 6: A subcubic bipartite series-parallel graph that cannot be drawn on
few lines. Figure 7: Recursive construction of $A_{i}$ (left) and $B_{i}$
(right)

We will recursively construct two families of series-parallel graphs $A_{i}$
and $B_{i}$ that cannot be drawn on a bounded number of lines. fig:serpar
shows the graph $B_{5}$ from this family. To construct these graphs, let
$A_{1}$ be a series-parallel graph with one edge and two terminal vertices.
Then:

  * •

For each $i\geq 1$, let $B_{i}$ be the graph formed as the parallel
composition of two subgraphs, each of which is the series composition of an
edge, $A_{i}$, and another edge (fig:recurse, right).

  * •

For each $i>1$, let $A_{i}$ be the graph formed as the parallel composition of
two subgraphs, one of which is a single edge and the other of which is the
series composition of an edge, $B_{i-1}$, and another edge (fig:recurse,
left).

It follows by induction that these graphs are subcubic, with degree two at
their two terminals, and that they are bipartite, with a 2-coloring (shown in
the figure) in which the two terminals have different colors. In the figure,
the upper blue and lower yellow vertices are the terminals of a graph $B_{i}$
at some level of the construction, while the upper yellow and lower blue
vertices are the terminals of a graph $A_{i}$ at some level of the
construction.

Because they are 2-vertex-connected but not 3-vertex-connected, these graphs
have many planar embeddings. The planar embeddings of any 2-connected graph
may be understood in terms of its SPQR tree [18], which in the case of a
series-parallel graph is more or less the same as the expression tree of
series and parallel compositions from which it was formed (associating
consecutive compositions of the same type into a single multi-operand
operation). Because of this equivalence, the embeddings of the graphs $A_{i}$
and $B_{i}$ may be generated from the embedding shown in the figure by two
types of change: any collection of subgraphs connecting two opposite terminals
of the graph may be flipped, giving a mirror-image embedding of that subgraph
within the larger graph, and any face of the resulting embedding may be chosen
as the outer face. We will show that these embeddings always contain large
nested sets of hexagons; this property forms the basis for our argument about
drawings on few lines.

Figure 8: Illustration for lem:sp-nest. No matter how $A_{i}$ is embedded, it
will contain a 6-cycle (red) surrounding one of the copies of $A_{i-1}$ from
which it is formed.

######  Lemma 3.1.

Every planar embedding of $A_{i}$ in which the two terminals belong to the
outer face contains a $(6,i-1)$-nest.

######  Proof 3.2.

For $i=1$, a $(6,i-1)$-nest consists of a single point (the egg), and the
result follows trivially. Otherwise, let $s$ and $t$ be the two terminals of
the $B_{i-1}$ subgraph from which the given $A_{i}$ graph is formed
(fig:surrounded). Then, in the $A_{i}$ graph, there are three length-three
paths from $s$ to $t$: one through the two terminals of the $A_{i}$ graph, and
one through each of the two $A_{i-1}$ subgraphs from which the $B_{i-1}$
subgraph is formed.

By the assumption that the two terminals of $A_{i}$ belong to the outer face,
there is a six-vertex cycle combining two of these three length-three paths,
one through the two terminals of $A_{i}$ and one through one of the copies of
$A_{i-1}$, that surrounds the other copy of $A_{i-1}$. By induction, this
surrounded copy contains a $(6,i-2)$-nest, which together with the cycle that
surrounds it forms a $(6,i-1)$-nest.

######  Lemma 3.3.

Let $j\leq i$ be two positive integers. Then every planar embedding of $B_{i}$
contains at least $2^{j}-1$ disjointly-embedded $(6,i-j)$-nests.

######  Proof 3.4.

$B_{j}$ is recursively constructed from $2^{j}$ copies of $A_{i-j+1}$. At most
one of these copies can contain the outer face of the embedding, so at least
$2^{j}-1$ copies are embedded with their two terminals outermost. The result
follows from lem:sp-nest.

######  Proof 3.5 (Proof of thm:treelike, series-parallel case).

The theorem claims that there exists a cubic bipartite series-parallel graph
that cannot be drawn on $\ell$ lines. To prove this, choose $j$ such that
$2^{j}\geq\tbinom{\ell}{2}+2$ and choose $i$ such that $i-j\geq 3\ell/2+2$. We
claim that, for this case, $B_{i}$ has the required properties. By lem:sp-
many-nests, it contains at least $\tbinom{\ell}{2}+1$ disjointly embedded
$(6,i-j)$-nests, enough to ensure that at least one of them does not contain
any crossing points of any given arrangement of $\ell$ lines. By lem:deep-
nest, a nest of this depth that does not contain any crossing points cannot be
drawn with its vertices on $\ell$ lines.

##  4 Apex-tree graphs

###  4.1 Apex-tree graphs requiring many lines

fig:apex-tree depicts a graph in the form of a tree (blue and yellow vertices)
plus one additional vertex (red); such a graph has been called an _apex-tree_
, and the additional vertex is the _apex_ The tree in the figure can be
constructed from the series-parallel graph $B_{4}$ of the previous section by
contracting half of the vertices (one vertex from each pair of terminals) into
a single supervertex. Alternatively, it can be constructed from a complete
binary tree by subdividing every non-leaf edge and then connecting each
subdivision vertex and each leaf vertex to the apex. These graphs are subcubic
except at the apex, and bipartite.

Figure 9: An apex-tree graph, subcubic except at the apex, that cannot be
drawn on few lines.

As with the earlier series-parallel graphs, we will prove that these graphs
cannot be drawn on a sublogarithmic number of lines. An obstacle to the proof,
however, is that they contain no $(p,r)$-nests for $r>1$, nor can any such
nest exist in any apex-tree. The reason is that, in an apex-tree, all cycles
contain the apex. Therefore, there can be no two disjoint cycles, and no nests
of two or more disjoint cycles. Nevertheless, these graphs do contain nest-
like structures. We define a _$(p,r)$ -near nest_ in an embedded plane graph
to be a collection of $p$ $r$-cycles, plus one additional vertex (the egg),
such that all cycles contain the egg in their interior, the cycles are edge-
disjoint, and any two of them share at most one vertex with each other. Then
the following lemma is an analogue of lem:deep-nest for near-nests:

######  Lemma 4.1.

Let $\mathcal{A}$ be an arrangement of $\ell$ lines, let $p$ and $r$ be
positive integers, and suppose that $r-1>\ell\cdot\lfloor p/2\rfloor$. Then it
is not possible to draw a $(p,r)$-near-nest in such a way that the polygon
vertices of the nest and its egg all lie on lines of $\mathcal{A}$.

######  Proof 4.2.

Suppose for a contradiction that we have drawn a $(p,r)$-near-nest with all
points on lines of $\mathcal{A}$. Let $\mathcal{S}$ be the system of disjoint
open line segments formed by intersecting the lines of $\mathcal{A}$ with the
outer polygon of the nest. Then $|S|\leq\ell\cdot\lfloor p/2\rfloor$ by
cor:few-segs, and each of the $r-1$ remaining polygons of the nest use up at
least one of the segments of $\mathcal{S}$ by lem:use-two and by the fact that
at most one of the two extreme segments of the polygon can be shared with
other polygons interior to it. Therefore, if $r-1>\ell\cdot\lfloor p/2\rfloor$
(as we supposed in the statement of the lemma), there will be no segments
remaining for the egg to lie on. Therefore, a drawing meeting these conditions
is impossible.

Analogously to lem:sp-nest and lem:sp-many-nests, we have:

######  Lemma 4.3.

For every planar embedding of a graph like the one of fig:apex-tree formed
from a complete binary tree of height $i$, and for every $j\leq i$, the
embedding contains $2^{j}-1$ disjoint $(4,i-j)$-near-nests.

######  Proof 4.4.

This result follows immediately from lem:sp-many-nests, which proves the
existence of a $(6,i-j)$-nest in the corresponding series-parallel graphs,
together with the observations that every planar embedding of our apex-trees
can be expanded to a planar embedding of the corresponding series-parallel
graphs, and that every 6-cycle of a $(6,i-j)$-nest in the expanded series-
parallel graph has three of its vertices contracted into the apex of the apex-
tree graph.

Alternatively, one could prove the result by repeating the proof of lem:sp-
many-nests with minor modifications.

######  Proof 4.5 (Proof of thm:treelike, apex-tree case).

The theorem claims that there exists a bipartite apex-tree graph, subcubic
except at its apex, that cannot be drawn on $\ell$ lines. To prove this,
choose $j$ such that $2^{j}\geq\tbinom{\ell}{2}+2$ and choose $i$ such that
$i-j-1>2\ell$. Form an apex-tree graph as above from a complete binary tree of
height $i$. We claim that, for this case, the resulting apex-tree graph has
the required properties. For, by lem:at-many-nests, it contains at least
$\tbinom{\ell}{2}+1$ disjointly embedded $(4,i-j)$-near-nests, enough to
ensure that at least one of them does not contain any crossing points of any
given arrangement of $\ell$-lines. By lem:deep-near-nest, a nest of this depth
that does not contain any crossing points of the $\ell$ lines cannot be drawn
with its vertices on the lines.

###  4.2 Drawing apex-tree graphs on few lines

Recall that thm:apex-tree-draw states that we can draw any apex-tree graph
planarly on $O(\log n)$ parallel lines. To do so, we adapt a standard tool
from tree drawing, the _heavy path decomposition_ [20], to draw any tree with
its vertices on the points of a grid of height $\log_{2}n$ and width $n$ (in
particular, on $O(\log n)$ horizontal lines) in such a way that the resulting
drawing can be extended to a drawing of an apex-tree, by adding one more
vertex adjacent to any subset of the tree vertices.

The heavy path decomposition of a tree is obtained by choosing one _heavy
edge_ for each non-leaf vertex of the tree, an edge connecting it to the
subtree with the largest number of vertices (breaking ties arbitrarily). The
connected components of the subgraph formed by the heavy edges are _heavy
paths_ , including as a special case length-zero paths for leaf vertices that
were not chosen by their parent. The heavy paths partition the vertices of the
tree. By induction, a vertex $v$ that can reach a leaf by a path that includes
$i$ non-heavy edges must be the root of a subtree containing at least
$2^{i+1}-1$ vertices (including $v$ itself). Therefore, in a tree with $n>1$
vertices, every root-to-leaf path contains at most $\log_{2}n-1$ non-heavy
edges.

Figure 10: Drawing an apex-tree on a grid. The thick horizontal black lines
depict the heavy path decomposition of the given tree. Note that although the
grid size is approximately $(n+\log_{2}n)\times n$, only the bottom
$\log_{2}n$ horizontal grid lines and the top horizontal grid line are
occupied by vertices.

######  Proof 4.6 (Proof of thm:apex-tree-draw).

To draw the given tree on a grid, we traverse the tree in preorder, ordering
the children at each vertex so that the heavy edge is last. We let the
$x$-coordinate of each vertex be its position in this preorder listing, and we
let the $y$-coordinate be the number of non-heavy edges on the path from the
vertex to the root. These choices give unique coordinates for each vertex on a
grid of height $\log_{2}n$ and width $n$, as claimed. Each tree edge either
connects two consecutive vertices on the same level of the grid (on the same
heavy path), or it connects vertices on consecutive levels (a parent and child
not connected by a heavy edge) whose $x$-coordinates both are less than the
next vertex on the same level as the parent. Therefore, the drawing has no
crossings.

All edges of this tree drawing have slope in the interval $[0,1]$. The
traversal ordering ensures that, for each vertex $v$, and each vertex $w$ with
a higher $y$-coordinate than $v$, one of the following is true: $w$ has
smaller $x$-coordinate than $v$, $w$ is a descendant of $v$, or $w$ is a
descendant of a vertex that is placed below and to the right of $v$. In all
three cases, neither $w$ nor any edge incident to $w$ can block the visibility
from $v$ upwards and to the right through lines of slope greater than one.
Therefore, if we place the apex $n+1$ units above the upper right corner of
the grid, it will be visible to all tree vertices by unobstructed lines of
sight and we can complete the drawing of any apex-tree consisting of the given
tree and one apex.

The construction is depicted in fig:apex-tree-grid.

##  5 Conclusions and open problems

We have found planar 3-regular bipartite graphs of size cubic in $\ell$ that
cannot be drawn on $\ell$ lines, cubic bipartite series-parallel graphs of
size exponential in $\ell$ that cannot be drawn on $\ell$ lines, and apex-
trees of size exponential in $\ell$ that cannot be drawn on $\ell$ lines. For
apex-trees the exponential size bound is necessary, although there may still
be room for tightening the gap between the exponential upper and lower bounds.
For the other two classes of graphs, we do not know whether our results are
tight. Stefan Felsner and Alexander Wolff have recently proven that every
4-vertex-connected maximal planar graph of size at most quadratic in $\ell$
may be drawn on $\ell$ pseudolines, and that it is NP-hard to find drawings on
two lines [3]. Do there exist planar graphs of subcubic size that cannot be
drawn on $\ell$ lines? Do there exist series-parallel graphs of polynomial
size that cannot be drawn on $\ell$ lines? How well can the optimal number of
lines be approximated? We leave these problems as open for future research.

## References

  * [1] Hans-Jürgen Bandelt, Victor Chepoi, and David Eppstein.  Combinatorics and geometry of finite and infinite squaregraphs.  SIAM Journal on Discrete Mathematics, 24(4):1399–1440, 2010.  http://dx.doi.org/10.1137/090760301 doi:10.1137/090760301.
  * [2] Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood.  Track layouts, layered path decompositions, and leveled planarity.  Algorithmica, 2018.  http://arxiv.org/abs/1506.09145 arXiv:1506.09145, http://dx.doi.org/10.1007/s00453-018-0487-5 doi:10.1007/s00453-018-0487-5.
  * [3] Therese Biedl, William Evans, Stefan Felsner, Sylvain Lazard, Henk Meijer, Pavel Valtr, Sue Whitesides, Steve Wismath, and Alexander Wolff.  Line and plane cover numbers revisited.  Manuscript, 2019.
  * [4] Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff.  The complexity of drawing graphs on few lines and few planes.  In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures: 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017, Proceedings, volume 10389 of Lecture Notes in Computer Science, pages 265–276. Springer, 2017.  http://arxiv.org/abs/1607.06444 arXiv:1607.06444, http://dx.doi.org/10.1007/978-3-319-62127-2_23 doi:10.1007/978-3-319-62127-2_23.
  * [5] Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Oleg Verbitsky, and Alexander Wolff.  Drawing graphs on few lines and few planes.  In Yifan Hu and Martin Nöllenburg, editors, Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19–21, 2016, Revised Selected Papers, volume 9801 of Lecture Notes in Computer Science, pages 166–180. Springer, 2016.  http://arxiv.org/abs/1607.01196 arXiv:1607.01196, http://dx.doi.org/10.1007/978-3-319-50106-2_14 doi:10.1007/978-3-319-50106-2_14.
  * [6] Danny Dolev, Tom Leighton, and Howard Trickey.  Planar embedding of planar graphs.  Advances in Computing Research, 2:147–161, 1984.  URL: https://noodle.cs.huji.ac.il/ dolev/pubs/planar-embed.pdf.
  * [7] Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood.  Minor-closed graph classes with bounded layered pathwidth.  in preparation, 2018.
  * [8] Vida Dujmović, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances Rosamond, Sue Whitesides, and David R. Wood.  On the parameterized complexity of layered graph drawing.  Algorithmica, 52(2):267–292, 2008.  http://dx.doi.org/10.1007/s00453-007-9151-1 doi:10.1007/s00453-007-9151-1.
  * [9] Vida Dujmović, Pat Morin, and David R. Wood.  Path-width and three-dimensional straight-line grid drawings of graphs.  In Michael T. Goodrich and Stephen G. Kobourov, editors, Graph Drawing: 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, volume 2528 of Lecture Notes in Computer Science, pages 42–53. Springer, 2002.  http://dx.doi.org/10.1007/3-540-36151-0_5 doi:10.1007/3-540-36151-0_5.
  * [10] Vida Dujmović, Attila Pór, and David R. Wood.  Track layouts of graphs.  Discrete Math. Theor. Comput. Sci., 6(2):497–521, 2004.
  * [11] Vida Dujmović and David R. Wood.  Stacks, queues and tracks: layouts of graph subdivisions.  Discrete Math. Theor. Comput. Sci., 7(1):155–201, 2005.
  * [12] Peter Eades and Sue Whitesides.  Drawing graphs in two layers.  Theoretical Computer Science, 131(2):361–374, 1994.  http://dx.doi.org/10.1016/0304-3975(94)90179-1 doi:10.1016/0304-3975(94)90179-1.
  * [13] Peter Eades and Nicholas C. Wormald.  Edge crossings in drawings of bipartite graphs.  Algorithmica, 11(4):379–403, 1994.  http://dx.doi.org/10.1007/BF01187020 doi:10.1007/BF01187020.
  * [14] David Eppstein.  Forbidden Configurations in Discrete Geometry.  Cambridge University Press, 2018.  Theorem 16.13.
  * [15] Stefan Felsner, Giuseppe Liotta, and Stephen Wismath.  Straight-line drawings on restricted integer grids in two and three dimensions.  Journal of Graph Algorithms and Applications, 7(4):363–398, 2003\.  http://dx.doi.org/10.7155/jgaa.00075 doi:10.7155/jgaa.00075.
  * [16] Oksana Firman, Fabian Lipp, Laura Straube, and Alexander Wolff.  Examining weak line covers with two lines in the plane (poster abstract).  In Graph Drawing and Network Visualization: 26th International Symposium, GD 2018, Barcelona, Spain, September 26–28, 2018, Revised Selected Papers, Lecture Notes in Computer Science. Springer, 2018.  to appear.
  * [17] Fabrizio Frati and Maurizio Patrignani.  A note on minimum-area straight-line drawings of planar graphs.  In Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers, volume 4875 of Lecture Notes in Computer Science, pages 339–344. Springer, 2008.  http://dx.doi.org/10.1007/978-3-540-77537-9_33 doi:10.1007/978-3-540-77537-9_33.
  * [18] Saunders Mac Lane.  A structural characterization of planar combinatorial graphs.  Duke Mathematical Journal, 3(3):460–472, 1937.  http://dx.doi.org/10.1215/S0012-7094-37-00336-3 doi:10.1215/S0012-7094-37-00336-3.
  * [19] Alexander Ravsky and Oleg Verbitsky.  On collinear sets in straight-line drawings.  In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21–24, 2011, Revised Papers, volume 6986 of Lecture Notes in Computer Science, pages 295–306. Springer, 2011.  http://arxiv.org/abs/0806.0253 arXiv:0806.0253, http://dx.doi.org/10.1007/978-3-642-25870-1_27 doi:10.1007/978-3-642-25870-1_27.
  * [20] Daniel D. Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  Journal of Computer and System Sciences, 26(3):362–391, 1983\.  http://dx.doi.org/10.1016/0022-0000(83)90006-5 doi:10.1016/0022-0000(83)90006-5.


# Dark Matter Admixed Neutron Star in the light of HESS J1731-347 and PSR
J0952-0607

Pinku Routaray1, H C Das 2, , Jeet Amrit Pattnaik2, Bharat Kumar1, ,
1 Department of Physics and Astronomy, National Institute of Technology,
Rourkela 769008, India
2 Institute of Physics, Sachivalaya Marg, Bhubaneswar 751005, India
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This study explores the implications of Dark Matter in Neutron Stars (DMANS)
by focusing on two specific astronomical objects: HESS J1731-347 and PSR
J0952-0607. Varying the Fermi momentum k$f^{\rm DM}$ of DM, the study analyzes
the EOS for the INRS model with and without DM. Results show the robustness of
the model, with most EOS curves within chiral Effective Field Theory bounds.
Our model predicts a maximum mass of $2.343\ M_{\odot}$ for PSR J0952-0607,
satisfying NICER bounds. The analysis suggests HESS J1731-347 could be a
DMANS. Constraints on DM within NSs are established, and tidal deformability
lies within GW event limits. Nonradial $f$-mode oscillations increase with DM,
concluding low mass stars pulsate at higher frequencies.

##  1 Introduction

In the last decades, significant progress has been achieved in understanding
the properties of compact stars, such as mass, radius, and tidal deformability
(Hinderer, 2008). This advancement enhances the exploration of the highly
dense neutron star (NS) and, at the same time, it restricts different
theories. One pivotal breakthrough came from the observation of gravitational
waves (GWs) from the merger of two NSs in the GW170817 event (Abbott et al.,
2017). This observation provided valuable insights into the masses of binary
systems and their tidal deformabilities. Another binary coalescence event,
GW190814 (Abbott et al., 2020b), involving a black hole and a compact object
with a mass range of 2.50-2.67 $M_{\odot}$, has raised a compelling argument
about the nature of the secondary compact object-whether it is the lightest
black hole or a massive NS.

In addition to GWs observations, there are concurrent measurements of mass and
radius of PSR J0030+0451 have been made through pulse profile modeling of
X-ray emissions from hot spots on the surface of the isolated NS observed by
Neutron Star Interior Composition Explorer (NICER) telescope (Riley et al.,
2019; Miller et al., 2019). The discovery of the Galactic NS (PSR J0952-0607),
named the “Black widow pulsar", has been unveiled in the Milky Way disc. It
has been distinguished as the fastest and heaviest of its kind, having a mass
of $M=2.35\pm 0.17\ M_{\odot}$ (Romani et al., 2022). Recently, a central
compact object within the supernova remnant HESS J1731-347 was investigated
through the analysis of its X-ray spectrum, revealing it to be a low-mass
object (Doroshenko et al., 2022). Remarkably, its mass has been determined to
be $M=0.77^{+0.20}_{-0.17}\ M_{\odot}$ having radius $10.4^{+0.86}_{-0.78}$
km, and it opens a debate whether this object is either the lightest NS or a
strange star with a more exotic equation of state (EOS).

Several studies have already hypothesized the nature of the HESS object. For
example, Horvath et al. (Horvath et al., 2023) employed the quark model and
lead to the conclusion that the object might be a light strange star. The
notion of a strange nature for HESS J1731-347 was also put forth in Refs.
(Clemente et al., 2023; Das & Lopes, 2023; Rather et al., 2023). On the other
hand, some works proposed it might be the lightest NS. For example, Kubis et
al. incorporated the $\omega-\delta$ cross-coupling into their established a
new relativistic mean-field (RMF) model by varying the slope parameter, which
satisfied the HESS constraints (Zabari et al., 2019; Kubis et al., 2023).
Additionally, Huang et al. (Huang et al., 2023) explored the possibility of
the lightest NS by considering the RMF model with tensor coupling. A
comprehensive study by Sagun et al. (Sagun et al., 2023) explored the nature
of the CCO in HESS as baryonic, strange, or even admixed with dark matter
(DM), particularly a two-fluid approach. Hence, there is still a window to
explore the nature of the HESS object.

In contrast to the aforementioned efforts, this study introduces a novel
approach to studying the CCO in HESS J1731-347, specifically focusing on the
inclusion of a DM admixed NS (DMANS) within a single fluid framework. This
study begins by formulating a new RMF model called “INRS" (IOP-NITR-SOA),
which is formulated to reproduce the mass ($M=2.35\ M_{\odot}$) of PSR
J0952-0607 (Romani et al., 2022). In addition, we also incorporate the DM
inside the NS, which satisfies several observational constraints that depends
on the amount of DM present inside it. These constraints include the $2\
M_{\odot}$ upper limit, as well as constraints imposed by NICER (Riley et al.,
2019; Miller et al., 2019), the multimessenger observation for canonical
radius as discussed in Capano et al. (2020), the stringent constraint imposed
by HESS J1731-347 (Doroshenko et al., 2022), and the tidal deformability
constraints given by GW170817 (Abbott et al., 2017) and GW190814 (Abbott et
al., 2020b) events. By considering these constraints, we want to fix the
amount of DM that could exist inside the NS. The oscillation frequency of the
NS is also a crucial quantity that can be used to explore the star’s internal
structure (Andersson & Kokkotas, 1996; Kunjipurayil et al., 2022; Sen et al.,
2023; Das et al., 2021a; Routaray et al., 2023b; Pradhan & Chatterjee, 2021).
Therefore, we also calculate the non-radial oscillation frequency within the
relativistic Cowling framework.

##  2 The Model

###  2.1 RMF model

Within the framework of relativistic mean field (RMF) formalism, we develop a
new model named "INRS" (IOP-NITR-SOA). The Lagrangian density of the RMF model
is given by (Furnstahl et al., 1996, 1997; Singh et al., 2014; Kumar et al.,
2017b, 2018),

$\displaystyle{\cal L}_{\rm nucl.}$ $\displaystyle=$
$\displaystyle\sum_{\alpha=p,n}\bar{\psi}_{\alpha}\Bigg{\\{}\gamma_{\mu}\bigg{(}i\partial^{\mu}-g_{\omega}\omega^{\mu}-\frac{1}{2}g_{\rho}\vec{\tau}_{\alpha}\\!\cdot\\!\vec{\rho}^{\,\mu}\bigg{)}$
(1) $\displaystyle-\bigg{(}M_{\rm
nucl.}-g_{\sigma}\sigma\bigg{)}\Bigg{\\}}\psi_{\alpha}+\frac{1}{2}\partial^{\mu}\sigma\,\partial_{\mu}\sigma-\frac{1}{2}m_{\sigma}^{2}\sigma^{2}$
$\displaystyle+\frac{\zeta_{0}}{4!}g_{\omega}^{2}(\omega^{\mu}\omega_{\mu})^{2}-\frac{\kappa_{3}}{3!}\frac{g_{\sigma}m_{\sigma}^{2}\sigma^{3}}{M_{nucl.}}-\frac{\kappa_{4}}{4!}\frac{g_{\sigma}^{2}m_{\sigma}^{2}\sigma^{4}}{M_{nucl.}^{2}}$
$\displaystyle+\frac{1}{2}m_{\omega}^{2}\omega^{\mu}\omega_{\mu}-\frac{1}{4}W^{\mu\nu}W_{\mu\nu}+\frac{1}{2}m_{\rho}^{2}\bigg{(}\vec{\rho}^{\mu}\\!\cdot\\!\vec{\rho}_{\mu}\bigg{)}$
$\displaystyle-\frac{1}{4}\vec{R}^{\mu\nu}\\!\cdot\\!\vec{R}_{\mu\nu}-\Lambda_{\omega}g_{\omega}^{2}g_{\rho}^{2}\big{(}\omega^{\mu}\omega_{\mu}\big{)}\big{(}\vec{\rho}^{\,\mu}\\!\cdot\\!\vec{\rho}_{\mu}\big{)}\,.$

The INRS model employed in this study was successfully calibrated using the
simulation annealing method, allowing for precise determination of its various
parameters of the RMF model, as mentioned above. The detailed parameterization
procedure has been extensively described in the references (Agrawal et al.,
2005; Kumar et al., 2006, 2017b, 2018). To achieve this calibration, coupling
constants and nuclear matter properties were carefully fitted by employing
experimental data on binding energy and charge radii for 16O, 40Ca, 48Ca,
68Ni, 90Zr, 100Sn, 132Sn, and 208Pb nuclei. The resulting values of these
calibrated parameters are summarized in Table 1. This rigorous calibration
process ensures that the INRS model accurately represents the properties of
neutron stars, both with and without the presence of dark matter, providing a
reliable and consistent framework for our investigation.

The above Lagrangian density can be solved in mean field approach using beta
equilibrium condition and from stress energy-momentum tensor we can calculate
the energy density (${\cal{E}}_{\rm NS}$) and pressure ($P_{\rm NS}$) for the
NS (Kumar et al., 2018).

$\displaystyle{\cal{E}}_{\rm NS}$ $\displaystyle=$
$\displaystyle\frac{2}{(2\pi)^{3}}\int d^{3}kE_{i}^{\ast}(k)+\rho
W+\frac{m_{s}^{2}\Phi^{2}}{g_{s}^{2}}\Bigg{(}\frac{1}{2}+\frac{\kappa_{3}}{3!}\frac{\Phi}{M}+\frac{\kappa_{4}}{4!}\frac{\Phi^{2}}{M^{2}}\Bigg{)}$
$\displaystyle-\frac{1}{2}m_{\omega}^{2}\frac{W^{2}}{g_{\omega}^{2}}-\frac{1}{4!}\frac{\zeta_{0}W^{4}}{g_{\omega}^{2}}+\frac{1}{2}\rho_{3}R-\frac{1}{2}\frac{m_{\rho}^{2}}{g_{\rho}^{2}}R^{2}-\Lambda_{\omega}(R^{2}\times
W^{2})$ (2) $\displaystyle P_{\rm NS}$ $\displaystyle=$
$\displaystyle\frac{2}{3(2\pi)^{3}}\int
d^{3}k\frac{k^{2}}{E_{i}^{\ast}(k)}-\frac{m_{s}^{2}\Phi^{2}}{g_{s}^{2}}\Bigg{(}\frac{1}{2}+\frac{\kappa_{3}}{3!}\frac{\Phi}{M}+\frac{\kappa_{4}}{4!}\frac{\Phi^{2}}{M^{2}}\Bigg{)}$
(3)
$\displaystyle+\frac{1}{2}m_{\omega}^{2}\frac{W^{2}}{g_{\omega}^{2}}+\frac{1}{4!}\frac{\zeta_{0}W^{4}}{g_{\omega}^{2}}+\frac{1}{2}\frac{m_{\rho}^{2}}{g_{\rho}^{2}}R^{2}+\Lambda_{\omega}(R^{2}\times
W^{2})$

Where $\Phi$, $W$ and $R$ are the fields associated with $\sigma$, $\omega$
and $\rho$ mesons respectively.

Table 1: Different parameters of "INRS" model is shown along with its nuclear matter properties. Mass of the $\sigma$,$\omega$ and $\rho$ mesons are presented in MeV. Parameter | $m_{\sigma}$ | $m_{\omega}$ | $m_{\rho}$ | $g_{\sigma}$ | $g_{\omega}$ | $g_{\rho}$ | $\kappa_{3}$ | $\kappa_{4}$ | $\zeta_{0}$ | $\Lambda_{\omega}$
---|---|---|---|---|---|---|---|---|---|---
INRS | 492.988 | 782.5 | 763.0 | 9.869 | 12.682 | 10.296 | 1.724 | -5.764 | 1.189 | 0.0156
$\rho_{0}$ (fm-3) |  |  $\mathcal{E}_{0}$ (MeV) |  |  $K$ (MeV) |  |  $J$ (MeV) |  |  $L$ (MeV) |  |
0.155 |  | -16.34 |  | 225.12 |  | 36.094 |  | 78.474 |  |

###  2.2 Model for the NS with DM admixed

The exploration of the true nature of DM remains an ongoing challenge in the
field of cosmology. Over the course of many years since the Big Bang, numerous
DM candidates have been proposed, with weakly interacting massive particles
(WIMPs) gaining significant popularity due to their thermal relic nature. In
our study, we focus on a specific class of WIMPs, known as non-annihilating
WIMPs or neutralinos, which we consider a potential candidate for dark matter.
These neutralinos are hypothesized to have already accreted within the NS due
to their high baryon density and enormous gravitational potential (Kouvaris &
Tinyakov, 2011; Goldman & Nussinov, 1989; Das et al., 2019).

To elucidate the nature of DMANS, we construct a Lagrangian density within the
framework of the standard model (SM). This Lagrangian density accounts for the
coupling between baryons and dark matter, involving Higgs exchange. The
formulation is influenced by previous works (Panotopoulos & Lopes, 2017; Das
et al., 2019; Das et al., 2020; Das et al., 2021b, a; Routaray et al., 2023b,
a) and is as follows:

$\displaystyle{\cal{L}}_{\rm DM}$ $\displaystyle=$
$\displaystyle\bar{\chi}\left[i\gamma^{\mu}\partial_{\mu}-M_{\chi}+yh\right]\chi+\frac{1}{2}\partial_{\mu}h\partial^{\mu}h$
(4) $\displaystyle-\frac{1}{2}M_{h}^{2}h^{2}+f\frac{M_{\rm
nucl.}}{v}\bar{\varphi}h\varphi\,,$

The symbols $\varphi$ and $\chi$ represent the nucleonic and dark matter wave
functions, respectively. The Higgs field is denoted by the symbol $h$. The
masses $M_{\chi}$ and $M_{h}$ represent the neutralino mass and Higgs mass,
respectively. The coupling constants between the DM and SM Higgs Bosons are
denoted as $y$. Consequently, $fM_{\rm nucl.}/v$ denotes the nucleon-Higgs
field effective Yukawa coupling with proton-Higgs form factor $f$ and vacuum
expectation of Higgs $v$.

The above Lagrangian can be solved to obtain the EOS for the DM and is given
by (Panotopoulos & Lopes, 2017; Das et al., 2020; Routaray et al., 2023b),

$\displaystyle{\cal{E}}_{\rm DM}=\frac{2}{(2\pi)^{3}}\int_{0}^{k_{f}^{\rm
DM}}d^{3}k\sqrt{k^{2}+(M_{\chi}^{\star})^{2}}+\frac{1}{2}M_{h}^{2}h_{0}^{2}\,,$
(5) $\displaystyle P_{\rm DM}=\frac{2}{3(2\pi)^{3}}\int_{0}^{k_{f}^{\rm
DM}}\frac{d^{3}k\hskip
2.84526ptk^{2}}{\sqrt{k^{2}+(M_{\chi}^{\star})^{2}}}-\frac{1}{2}M_{h}^{2}h_{0}^{2}\,,$
(6)

Where $M_{\chi}^{\star}$ represents the effective mass of the DM.

Hence, in the context of DMANS, the expressions for the total energy density
and pressure can be formulated as follows.

$\displaystyle{\cal{E}}={\cal{E}}_{\rm NS}+{\cal{E}}_{\rm DM}\,,$
$\displaystyle{\rm and}\hskip 28.45274ptP=P_{\rm NS}+P_{\rm DM}\,,$ (7)

Once the EOS is determined as an input, the Tolman–Oppenheimer–Volkoff (TOV)
equation can be solved to compute the mass and radius of the dark matter
admixed neutron star (Tolman, 1939; Oppenheimer & Volkoff, 1939; Routaray et
al., 2023b). And the calculation for the dimensionless tidal deformability
($\Lambda$) (Hinderer, 2008; Kumar et al., 2017a) and non-radial $f$-mode
oscillation (Kunjipurayil et al., 2022; Das et al., 2021a; Pradhan &
Chatterjee, 2021) can be done by solving their respective differential
equations along with the TOV equation.

##  3 Results and Discussion

Figure 1: Using the chiral EFT bound, which is shaded in pink color, the EOS
for the INRS model is plotted with and without DM. The inset plot shows how
the sound speed ($c_{s}^{2}$) varies with the density.

In Figure 1, we illustrate the EOS for the INRS model both with and without
the presence of dark matter. The shaded region represents the chiral Effective
Field Theory (EFT) bounds (Drischler et al., 2021), providing a benchmark for
our analysis. To assess the influence of DM, we explore various scenarios by
varying the Fermi momentum of the dark matter (k${}_{f}^{\rm DM}$) from $0.00$
GeV to $0.05$ GeV. Remarkably, nearly all of the EOS curves align within the
chiral EFT bounds, affirming the robustness and consistency of our model. It’s
important to note that the unified EOS is constructed using the SLY4 crust
(Douchin & Haensel, 2001). In addition to the main plot, we provide an inset
plot illustrating the sound speed as a function of density, ensuring that the
causality limit is satisfied. This ensures that the speed of sound within the
neutron star does not exceed the speed of light, thus preserving causality.

Figure 2: The mass-radius relation for our novel RMF model INRS is shown with and without DM along with different observational constraints. Table 2: Neutron star properties such as mass(M), radius(R), dimensionless tidal deformibility($\Lambda$) and nonradial $f$-mode frequency shown with varying k${}_{f}^{\rm DM}$.  $k_{f}^{\rm DM}$ (GeV) | $M=0.77M_{\odot}$ | $M=1.4M_{\odot}$ | $M=M_{\rm max}(M_{\odot})$
---|---|---|---
| $R$ | $\Lambda$ | $f$ | $R$ | $\Lambda$ | $f$ | $M$ | $R$ | $\Lambda$ | $f$
0.000 | 12.585 | 17328.172 | 1.741 | 13.040 | 732.105 | 2.013 | 2.343 | 12.164 | 9.757 | 2.392
0.005 | 12.573 | 17280.384 | 1.742 | 13.032 | 730.754 | 2.014 | 2.343 | 12.160 | 9.760 | 2.392
0.010 | 12.485 | 16944.979 | 1.753 | 12.975 | 720.574 | 2.021 | 2.336 | 12.134 | 9.802 | 2.396
0.015 | 12.268 | 16101.535 | 1.782 | 12.833 | 694.021 | 2.040 | 2.329 | 11.922 | 8.624 | 2.405
0.020 | 11.905 | 14688.758 | 1.834 | 12.587 | 646.907 | 2.076 | 2.311 | 11.790 | 8.672 | 2.424
0.025 | 11.426 | 12823.245 | 1.911 | 12.244 | 580.448 | 2.130 | 2.282 | 11.610 | 8.936 | 2.454
0.030 | 10.885 | 10758.035 | 2.012 | 11.827 | 499.789 | 2.206 | 2.240 | 11.316 | 8.783 | 2.523
0.035 | 10.323 | 8734.671 | 2.134 | 11.364 | 413.899 | 2.301 | 2.185 | 10.974 | 8.794 | 2.582
0.040 | 9.772 | 6906.368 | 2.276 | 10.881 | 330.210 | 2.415 | 2.119 | 10.580 | 8.785 | 2.682
0.045 | 9.247 | 5360.532 | 2.434 | 10.388 | 255.626 | 2.547 | 2.043 | 10.128 | 8.609 | 2.773
0.050 | 8.752 | 4101.288 | 2.608 | 9.900 | 190.975 | 2.694 | 1.959 | 9.690 | 8.895 | 2.907

The resulting mass and radius values are depicted in Figure 2, with the color
bar indicating the variation of k${}_{f}^{\rm DM}$ with a step of $0.005$ GeV.
In our analysis, we consider several observational constraints for mass and
radius. The mass constraints from the black widow pulsar PSR J0952-0607
(purple) (Romani et al., 2022), PSR J0348+0432 (blue) (Antoniadis et al.,
2013), and PSR J0740+6620 (orange) are represented by shaded regions.
Additionally, the radius constraints from NICER (Riley et al., 2019; Miller et
al., 2019) and multimessenger observation (Capano et al., 2020) are also taken
into account. Importantly, the mass-radius constraint from HESS J1731-347 is
represented by the pink shaded region (Doroshenko et al., 2022). As we
increase the value of k${}_{f}^{\rm DM}$, the maximum mass of the neutron star
decreases, and the resulting $M-R$ curve shifts towards the left. When
k${}_{f}^{\rm DM}$ is approximately $0.03$ GeV, the $M-R$ curve aligns well
with the observational data. At this specific value of k${}_{f}^{\rm DM}$, the
radius of the canonical star, as presented by both NICER and Capano et al., is
also satisfied. Furthermore, this k${}_{f}^{\rm DM}$ value also fulfills the
mass-radius constraint of HESS J1731-347. For larger values of k${}_{f}^{\rm
DM}$, up to $0.045$ GeV, the constraints of HESS J1731-347 and the canonical
radius for Capano et al. continue to be satisfied.

Figure 3: With varying the k${}_{f}^{\rm DM}$ the fluctuation of the
dimensionless tidal deformibility ($\Lambda$) with mass is explored. The
models we have developed are further validated through the utilisation of
GW170817 and GW190814.

In Figure 3, we present the calculated $\Lambda$ values for both the baryonic
and DM cases, providing essential insights into the impact of DM inclusion on
the deformability of the neutron star. The error bars in the plot represent
the estimated values for the tidal deformability of the canonical star, which
correspond to the values obtained from gravitational wave measurements of
GW170817 (Abbott et al., 2017) and GW190814 (Abbott et al., 2020a). The blue
shaded region corresponds to the constraints derived from the GW170817
measurements, and the color bar represents the variation of k${}_{f}^{\rm DM}$
in the GeV scale. From the figure, we observe that the tidal deformability
decreases with the inclusion of dark matter, indicating that an increased
amount of DM within the neutron star makes it more resistant to deformation in
response to tidal forces. This result aligns with our previous findings,
reinforcing the notion that dark matter has a significant impact on the
structural properties of neutron stars. Moreover, our EOS considered in this
study demonstrates remarkable consistency with the canonical bound of the
GW190814 event, as well as the observational constraint of GW170817, as
indicated by the blue shaded region.

Figure 4: The impacts of the k${}_{f}^{\rm DM}$ on the nonradial $f$-mode
frequency is shown as the function of mass. The theoretical limits of GW170817
and GW190814 also imposed.

In Figure 4, we present the variation of the nonradial $f$-mode oscillation
frequency with the mass of the neutron star. Notably, we also consider the
theoretical limits of the $f$-mode frequency in light of the gravitational
wave events GW170817 (Abbott et al., 2017) and GW190814 (Abbott et al.,
2020a). As we increase the parameter k${}_{f}^{\rm DM}$, we observe a
corresponding increase in the $f$-mode frequency, implying that the neutron
star pulsates with a higher frequency. This effect is consistent with the
trend of the maximum mass of the neutron star decreasing with the increase in
k${}_{f}^{\rm DM}$.

##  4 CONCLUSIONS

In this paper, we have investigated the implications of DMANS in the context
of two specific astronomical objects, namely HESS J1731-347 and PSR
J0952-0607. To explore the effects of DM, we varied the Fermi momentum
k${}_{f}^{\rm DM}$ of DM from 0.00 GeV to 0.05 GeV. Our analysis focused on
the EOS for the INRS model, both with and without the presence of dark matter.
We found that nearly all EOS curves remained within the chiral Effective Field
Theory bounds, demonstrating the robustness and consistency of our model. In
the presence of DM, the EOS became softer, affecting the mass and radius of
the NSs. However, without the inclusion of DM, our model successfully produced
a maximum mass of approximately $2.343\ M_{\odot}$ for PSR J0952-0607,
satisfying the NICER bounds for canonical radius. Furthermore, our analysis
also helped in determining the nature of HESS J1731-347, suggesting that it
could be a DMANS. We were able to constrain the amount of DM within the NSs
based on the bounds from HESS J1731-347. For a Fermi momentum k${}_{f}^{\rm
DM}$ of approximately 0.03 GeV, our model satisfied the constraints from HESS
J1731-347 as well as the radius constraint by Capano $et.al.$ Increasing the
value of k${}_{f}^{\rm DM}$ up to approximately 0.045 GeV still allowed our
model to satisfy these constraints. Moreover, we investigated the tidal
deformability of the NSs in our novel model, both with and without DM, and
found that the values lie within the limits of GW events. Finally, we
calculated the nonradial $f$-mode oscillation and observed that with the
inclusion of DM, the amplitude of the $f$-mode increased as the DM’s Fermi
momentum increased. The softening effect of the EOS due to the addition of DM
resulted in a decrease in the maximum mass of the NSs, leading to the
conclusion that a low mass star pulsates with a higher frequency than a high
mass star in our model.

##  5 Acknowledgments

B.K. acknowledges partial support from the Department of Science and
Technology, Government of India with grant no. CRG/2021/000101.

## DATA AVAILABILITY

This manuscript has no associated data, or the data will not be deposited.
Data sharing is not applicable to this article as no data sets were generated
or analyzed during the current study.

## References

  * Abbott et al. (2017) Abbott B. P., Abbott R., Abbott T. D., et al., 2017, Phys. Rev. Lett., 119, 161101
  * Abbott et al. (2020a) Abbott B. P., Abbott R., Abbott T. D., et al. 2020a, The Astrophysical Journal, 892, L3
  * Abbott et al. (2020b) Abbott R., Abbott T. D., Abraham S., et al., 2020b, The Astrophysical Journal, 896, L44
  * Agrawal et al. (2005) Agrawal B. K., Shlomo S., Au V. K., 2005, Phys. Rev. C, 72, 014310
  * Andersson & Kokkotas (1996) Andersson N., Kokkotas K. D., 1996, Phys. Rev. Lett., 77, 4134
  * Antoniadis et al. (2013) Antoniadis J., Freire P. C. C., Wex N., et al., 2013, Science, 340, 1233232
  * Capano et al. (2020) Capano C. D., Tews I., Brown S. M., et al., 2020, Nature Astronomy, 4, 625–632
  * Clemente et al. (2023) Clemente F. D., Drago A., Pagliara G., 2023, Is the compact object associated with HESS J1731-347 a strange quark star? (arXiv:2211.07485)
  * Das & Lopes (2023) Das H. C., Lopes L. L., 2023, Anisotropic Strange Stars in the Spotlight: Unveiling Constraints through Observational Data (arXiv:2306.00326)
  * Das et al. (2019) Das A., Malik T., Nayak A. C., 2019, Phys. Rev. D, 99, 043016
  * Das et al. (2020) Das H. C., Kumar A., Kumar B., Biswal S. K., Nakatsukasa T., Li A., Patra S. K., 2020, Monthly Notices of the Royal Astronomical Society, 495, 4893
  * Das et al. (2021a) Das H. C., Kumar A., Patra S. K., 2021a, Phys. Rev. D, 104, 063028
  * Das et al. (2021b) Das H., Kumar A., Kumar B., Biswal S., Patra S., 2021b, Journal of Cosmology and Astroparticle Physics, 2021, 007
  * Doroshenko et al. (2022) Doroshenko V., Suleimanov V., Pühlhofer G., Santangelo A., 2022, Nature Astronomy, 6, 1444
  * Douchin & Haensel (2001) Douchin F., Haensel P., 2001, A&A, 380, 151
  * Drischler et al. (2021) Drischler C., Han S., Lattimer J. M., Prakash M., Reddy S., Zhao T., 2021, Phys. Rev. C, 103, 045808
  * Furnstahl et al. (1996) Furnstahl R., Serot B. D., Tang H.-B., 1996, Nuclear Physics A, 598, 539
  * Furnstahl et al. (1997) Furnstahl R. J., Serot B. D., Tang H.-B., 1997, Nucl. Phys. A, 615, 441
  * Goldman & Nussinov (1989) Goldman I., Nussinov S., 1989, Phys. Rev. D, 40, 3221
  * Hinderer (2008) Hinderer T., 2008, The Astrophysical Journal, 677, 1216
  * Horvath et al. (2023) Horvath J. E., Rocha L. S., de Sá L. M., Moraes P. H. R. S., Barão L. G., de Avellar M. G. B., Bernardo A., Bachega R. R. A., 2023, Astronomy & Astrophysics, 672, L11
  * Huang et al. (2023) Huang K., Hu J., Zhang Y., Shen H., 2023, The hadronic equation of state of HESS J1731-347 from the relativistic mean-field model with tensor coupling (arXiv:2306.04992)
  * Kouvaris & Tinyakov (2011) Kouvaris C., Tinyakov P., 2011, Phys. Rev. D, 83, 083512
  * Kubis et al. (2023) Kubis S., Wójcik W., Castillo D. A., Zabari N., 2023, Relativistic mean field model for ultra-compact low mass neutron star of HESS J1731-347 (arXiv:2307.02979)
  * Kumar et al. (2006) Kumar R., Agrawal B. K., Dhiman S. K., 2006, Phys. Rev. C, 74, 034323
  * Kumar et al. (2017a) Kumar B., Biswal S. K., Patra S. K., 2017a, Phys. Rev. C, 95, 015801
  * Kumar et al. (2017b) Kumar B., Singh S., Agrawal B., Patra S., 2017b, Nuclear Physics A, 966, 197
  * Kumar et al. (2018) Kumar B., Patra S. K., Agrawal B. K., 2018, Phys. Rev. C, 97, 045806
  * Kunjipurayil et al. (2022) Kunjipurayil A., Zhao T., Kumar B., Agrawal B. K., Prakash M., 2022, Phys. Rev. D, 106, 063005
  * Miller et al. (2019) Miller M. C., et al., 2019, The Astrophysical Journal Letters, 887, L24
  * Oppenheimer & Volkoff (1939) Oppenheimer J. R., Volkoff G. M., 1939, Phys. Rev., 55, 374
  * Panotopoulos & Lopes (2017) Panotopoulos G., Lopes I., 2017, Phys. Rev. D, 96, 083004
  * Pradhan & Chatterjee (2021) Pradhan B. K., Chatterjee D., 2021, Phys. Rev. C, 103, 035810
  * Rather et al. (2023) Rather I. A., Panotopoulos G., Lopes I., 2023, Quark Models and Radial Oscillations: Decoding the HESS J1731-347 Compact Object’s Equation of State (arXiv:2307.03703)
  * Riley et al. (2019) Riley T. E., et al., 2019, The Astrophysical Journal Letters, 887, L21
  * Romani et al. (2022) Romani R. W., Kandel D., Filippenko A. V., Brink T. G., Zheng W., 2022, The Astrophysical Journal Letters, 934, L17
  * Routaray et al. (2023a) Routaray P., Mohanty S. R., Das H. C., Ghosh S., Kalita P. J., Parmar V., Kumar B., 2023a, Investigating Dark Matter-Admixed Neutron Stars with NITR Equation of State in Light of PSR J0952-0607 (arXiv:2304.05100)
  * Routaray et al. (2023b) Routaray P., Das H. C., Sen S., Kumar B., Panotopoulos G., Zhao T., 2023b, Phys. Rev. D, 107, 103039
  * Sagun et al. (2023) Sagun V., Giangrandi E., Dietrich T., Ivanytskyi O., Negreiros R., Providência C., 2023, What is the nature of the HESS J1731-347 compact object? (arXiv:2306.12326)
  * Sen et al. (2023) Sen S., Kumar S., Kunjipurayil A., Routaray P., Ghosh S., Kalita P. J., Zhao T., Kumar B., 2023, Galaxies, 11
  * Singh et al. (2014) Singh S. K., Biswal S. K., Bhuyan M., Patra S. K., 2014, Journal of Physics G: Nuclear and Particle Physics, 41, 055201
  * Tolman (1939) Tolman R. C., 1939, Phys. Rev., 55, 364
  * Zabari et al. (2019) Zabari N., Kubis S., Wójcik W., 2019, Phys. Rev. C, 100, 015808