text:
# Math Help - The dot notation in a probability distribution

1. ## The dot notation in a probability distribution

Hi guys, a new member here.

In a probability distribution like N(·|0,σ2) or GP(·|0,c) what do the dot and the vertical bar mean?

And anybody has any advice on how to search for such information? I spent about three hours reading papers and textbooks to find the meaning of this notation with no luck.

2. Originally Posted by Dever
Hi guys, a new member here.

In a probability distribution like N(·|0,σ2) or GP(·|0,c) what do the dot and the vertical bar mean?

And anybody has any advice on how to search for such information? I spent about three hours reading papers and textbooks to find the meaning of this notation with no luck.
That is because it is not a common notation.

The dot is usually a place holder for an unspecified variable of some kind. The vertical bar separates the parameters of the distribution (to the right) from whatever the dot represents. Your best bet to find what precisely is meant by this notation is to so to where it was introduced and see what it says there.

CB

format: plain


text:
# Embedding graphs into two-dimensional simplicial complexes

We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general. The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).

## Authors

• 4 publications
• 1 publication
• 15 publications
• ### Atomic Embeddability, Clustered Planarity, and Thickenability

We study the atomic embeddability testing problem, which is a common gen...
07/30/2019 ∙ by Radoslav Fulek, et al. ∙ 0

• ### Graph Pattern Matching Preserving Label-Repetition Constraints

Graph pattern matching is a routine process for a wide variety of applic...
04/12/2018 ∙ by Houari Mahfoud, et al. ∙ 0

• ### On the hardness of finding normal surfaces

There are fundamental topological problems, such as unknot recognition a...
12/19/2019 ∙ by Benjamin A. Burton, et al. ∙ 0

• ### Subgraph densities in a surface

Given a fixed graph H that embeds in a surface Σ, what is the maximum nu...
03/30/2020 ∙ by Tony Huynh, et al. ∙ 0

• ### On the dichromatic number of surfaces

In this paper, we give bounds on the dichromatic number χ⃗(Σ) of a surfa...
02/01/2021 ∙ by Pierre Aboulker, et al. ∙ 0

• ### An Experimental Study of a 1-planarity Testing and Embedding Algorithm

The definition of 1-planar graphs naturally extends graph planarity, nam...
11/01/2019 ∙ by Carla Binucci, et al. ∙ 0

• ### Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor

The notion of Turing kernelization investigates whether a polynomial-tim...
07/06/2017 ∙ by Bart M. P. Jansen, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

#### Topological embedding problems.

Topological embedding problems are among the most fundamental problems in computational topology, already emphasized since the early developments of this discipline [8, Section 10]. Their general form is as follows: Given topological spaces and , does there exist an embedding (a continuous, injective map) from  to ? Since a finite description of and  is needed, typically they are represented as finite simplicial complexes, which are topological spaces obtained by attaching simplices (points, segments, triangles, tetrahedra, etc.) of various dimensions together.

The case where the host space  equals  (or, almost equivalently, , which can be modeled as a simplicial complex) has been studied the most. The case corresponds to the planarity testing problem, which has attracted considerable interest [27]. The case is much harder, and has only recently been shown to be decidable by Matoušek, Sedgwick, Tancer, and Wagner [21]. The general problem for arbitrary  has been extensively studied in the last few years, starting with hardness results by Matoušek, Tancer, and Wagner [22], and continuing with some algorithmic results in a series of articles; we refer to Matoušek et al. [21, Introduction] for a state of the art.

What about more general choices of ? The case where is a graph is essentially the subgraph homeomorphism problem, asking if  contains a subdivision of a graph . This is hard in general, easy when  is fixed, and polynomial-time solvable for every fixed , by using graph minor algorithms. The case where is a graph and  a 2-dimensional simplicial complex that is homeomorphic to a surface has been much investigated, also in connection to topological graph theory [25] and algorithms for surface-embedded graphs [11, 7]: The problem is NP-complete, as proved by Thomassen [30], but Mohar [24] has proved that it can be solved in linear time if is fixed (in some recent works, the proof has been simplified and the result extended [15, 17]). The case where is a 2-complex and is (a 2-complex homeomorphic to) a surface essentially boils down to the previous case; see Mohar [23]. More recently, Čadek, Krčál, Matoušek, Vokřínek, and Wagner [4, Theorem 1.4] considered the case where the host complex  has an arbitrary (but fixed) dimension; they provide a polynomial-time algorithm for the related map extension problem, under some assumptions on the dimensions of and ; in particular, must have trivial fundamental group (because they manipulate in an essential way the homotopy groups of , which have to be Abelian); but the maps they consider need not be embeddings.

Another variation on this problem is to try to embed such that it extends a given partial embedding of (we shall consider such embedding extension problems later). This problem has already been studied in some particular cases; in particular, Angelini, Battista, Frati, Jelínek, Kratochvìl, Patrignani, and Rutter [1, Theorem 4.5] provide a linear-time algorithm to decide the embedding extension problem of a graph in the plane.

#### Our results.

In this article, we study the topological embedding problem when is an arbitrary graph , and is an arbitrary two-dimensional simplicial complex  (actually, a simplicial complex of dimension at most two—abbreviated as 2-complex below). Formally, we consider the following decision problem:

Embed:
Input: A graph  with vertices and edges, and a 2-complex  with simplices.
Question: Does have a topological embedding into ?

(We use the parameters and  whenever we need to refer to the input size.) Here are our main results:

###### Theorem 1.1.

The problem Embed is NP-complete.

###### Theorem 1.2.

The problem Embed can be solved in time , where is some computable function of .

As for Theorem 1.1, it is straightforward that the problem is NP-hard (as the case where is a surface is already NP-hard); the interesting part is to provide a certificate checkable in polynomial time when an embedding exists. Note that Theorem 1.2 shows that, for every fixed complex , the problem of deciding whether an input graph embeds into  is polynomial-time solvable. Actually, our algorithm is explicit, in the sense that, if there exists an embedding of  on , we can provide some representation of such an embedding (in contrast to some results in the theory of graph minors, where the existence of an embedding can be obtained without leading to an explicit construction).

#### Why do 2-complexes look harder than surfaces?

A key property of the class of graphs embeddable on a fixed surface is that it is minor-closed: Having a graph  embeddable on a surface , removing or contracting any edge yields a graph embeddable on . By Robertson and Seymour’s theory, this immediately implies a cubic-time algorithm to test whether a graph  embeds on , for every fixed surface  [28]. In contrast, the class of graphs embeddable on a fixed 2-complex is, in general, not closed under taking minors, and thus this theory does not apply. For example, let be obtained from two tori by connecting them together with a line segment, and let be obtained from two copies of  by joining them together with a new edge ; then embeds into , but the minor obtained from  by contracting  does not.

Two-dimensional simplicial complexes are topologically much more complicated than surfaces. For example, there exist linear-time algorithms to decide whether two surfaces are homeomorphic (this amounts to comparing the Euler characteristics, the orientability characters, and, in case of surfaces with boundary, the numbers of boundary components), or to decide whether a closed curve is contractible (see Dey and Guha [9], Lazarus and Rivaud [18], and Erickson and Whittlesey [12]). In contrast, the homeomorphism problem for 2-complexes is as hard as graph isomorphism, as shown by Ó Dúnlaing, Watt, and Wilkins [26]. Moreover, the contractibility problem for closed curves on 2-complexes is undecidable; even worse, there exists a fixed 2-complex  such that the contractibility problem for closed curves on  is undecidable (this is because every finitely presented group can be realized as the fundamental group of a 2-complex, and there is such a group in which the word problem is undecidable, by a result of Boone [3]; see also Stillwell [29, Section 9.3]).

Despite this stark contrast between surfaces and 2-complexes, if we care only on the polynomiality or non-polynomiality, our results show that the complexities of embedding a graph into a surface or a 2-complex are similar: If the host space is not fixed, the problem is NP-complete; otherwise, it is polynomial-time solvable. Compared to the aforementioned hard problems on general 2-complexes, one feature related to our result is that every graph embeds on a 3-book (a complex made of three triangles sharing a common edge); thus, we only need to consider 2-complexes without 3-book, for otherwise the problem is trivial; this significantly restricts the structure of the 2-complexes to be considered. The problem of whether Embed admits an algorithm that is fixed-parameter tractable in terms of the parameter , however, remains open for general complexes, whereas it is the case when restricting to surfaces [24].

#### Why is embedding graphs on 2-complexes interesting?

First, let us remark that, if we consider the problem of embedding graphs into simplicial complexes, then the case that we consider, in which the complex has dimension at most two, is the only interesting one, since every graph can be embedded in a single tetrahedron.

We have already noted that the problem we study is more general than the problem of embedding graphs on surfaces. It is indeed quite general, and some other problems studied in the past can be recast as an instance of Embed or as variants of it. For example, the crossing number of a graph  is the minimum number of crossings in a (topological) drawing of  in the plane. Deciding whether a graph  has crossing number at most  is NP-hard, but fixed-parameter tractable in , as shown by Kawarabayashi and Reed [16]. This is easily seen to be equivalent to the embeddability of  into the complex obtained by removing  disjoint disks from a sphere and adding, for each resulting boundary component , two edges with endpoints on  whose cyclic order along  is interlaced. Of course, the embeddability problem on a 2-complex is more general and contains, for example, the problem of deciding whether there is a drawing of a graph  on a surface of genus  with at most crossings. In topological graph theory, embeddings of graphs on pseudosurfaces (which are special 2-complexes) have been considered; see Archdeacon [2, Section 5.7] for a survey. Slightly more remotely, a book embedding of a graph  (see, e.g., Malik [20]) is also an embedding of  into a particular 2-complex, with additional constraints on the embedding.

#### Strategy of the proof and organization of the paper.

For clarity of exposition, in most of the paper, we focus on developing an algorithm for the problem Embed (Theorem 1.2). Only at the end (Section 8) we explain why our techniques imply that the problem is in NP. The idea of the algorithm is to progressively reduce the problem to simpler problems. We first deal with the case where the complex  contains a 3-book (Section 3). From Section 4 onwards, we reduce Embed to embedding extension problems (EEP), similar to the Embed problem except that an embedding of a subgraph  of the input graph  is already specified. In Section 4, we reduce Embed to EEPs on a pure 2-complex (in which every segment of the complex  is incident to at least one triangle). In Section 5, we further reduce it to EEPs on a surface. In Section 6, we reduce it to EEPs on a surface in which every face of the subgraph  is a disk. Finally, in Section 7, we show how to solve EEPs of the latter type using a key component in an algorithm by the third author [24] to decide embeddability of a graph on a surface.

## 2 Preliminaries

### 2.1 Embeddings of graphs into 2-complexes

A 2-complex is an abstract simplicial complex of dimension at most two: a finite set of 0-simplices called nodes, 1-simplices called segments, and 2-simplices called triangles (we use this terminology to distinguish from that of vertices and edges, which we reserve for graphs); each segment is a pair of nodes, and each triangle is a triple of nodes; moreover, each subset of size two in a triangle must be a segment. Each 2-complex  corresponds naturally to a topological space, obtained in the obvious way: Start with one point per node in ; connect them by segments as indicated by the segments in ; similarly, for every triangle in , create a triangle whose boundary is made of the three segments contained in that triangle. By abuse of language, we identify with that topological space. To emphasize that we consider the abstract simplicial complex and not only the topological space, we sometimes use the name triangulation or triangulated complex.

In this paper, graphs are finite, undirected, and may have loops and multiple edges. In a similar way as for 2-complexes, each graph has an associated topological space; an embedding of a graph  into a 2-complex  is an injective continuous map from (the topological space associated to) to (the topological space associated to) .

### 2.2 Structural aspects of 2-complexes

We say that a 2-complex contains a 3-book if some three distinct triangles share a common segment.

Let be a node of . A cone at  is a cyclic sequence of triangles , all incident to , such that, for each , the triangles and  share a segment incident with , and any other pair of triangles have only in common. A corner at  is an inclusionwise maximal sequence of triangles , all incident to , such that, for each , the triangles and  share a segment incident with , and any other pair of triangles have only in common. An isolated segment at  is a segment incident to  but not incident to any triangle.

If contains no 3-books, the set of segments and triangles incident with a given node  of  are uniquely partitioned into cones, corners, and isolated segments. We say that is a regular node if all the segments and triangles incident to  form a single cone or corner. Otherwise, is a singular node. A 2-complex is pure if it contains no isolated segment, and each node is incident to at least one segment.

### 2.3 Embedding extension problems and reductions

An embedding extension problem (EEP) is a decision problem defined as follows:

EEP:
Input: A graph  with vertices and edges, a subgraph  of  with vertices and edges, and an embedding  of  into a 2-complex  with simplices.
Question: Does have an embedding into  whose restriction to  is ?

To be precise, we will have to explain how we represent the embedding , but this will vary throughout the proof, and we will be more precise about this in subsequent sections. Let us simply remark that, since the complexity of our algorithm is a polynomial of large degree (depending on the complex ) in the size of the input graph, the choice of representation is not very important, because converting between any two reasonable representations is possible in polynomial time.

We will reduce our original problem to more and more specialized EEPs. We will use the word “reduce” in a somewhat sloppy sense: A decision problem  reduces to instances of the decision problem  if solving these instances of  allows to solve the instance of  in time . We will have to be more precise when we consider the NP-completeness of Embed in Section 8.

### 2.4 Surfaces

In Section 6, we will assume some familiarity with surface topology; see, e.g., [25, 29, 5] for suitable introductions under various viewpoints. We recall some basic definitions and properties. A surface is a compact, connected Hausdorff topological space in which every point has a neighborhood homeomorphic to the plane. Every surface  is obtained from a sphere by:

• either removing open disks and attaching a handle (a torus with an open disk removed) to each resulting boundary component, for an even, nonnegative number  called the (Euler) genus of ; in this case, is orientable;

• or removing open disks and attaching a Möbius band to each resulting boundary component, for a positive number  called the genus of ; in this case, is non-orientable.

A surface with boundary is obtained from a surface by removing a finite set of interiors of disjoint closed disks. The boundary of each disk forms a boundary component of . A possibly disconnected surface is a disjoint union of surfaces. An embedding of  into a surface , possibly with boundary, is cellular if each face of the embedding is homeomorphic to an open disk. If is cellularly embedded on a surface with genus  and boundary components, with  vertices,  edges, and  faces, then Euler’s formula stipulates that .

An ambient isotopy of a surface with boundary  is a continuous family of self-homeomorphisms of  such that is the identity.

## 3 Reduction to complexes containing no 3-book

The following folklore observation allows us to solve the problem trivially if  contains a 3-book. We include a proof for completeness.

###### Proposition 3.1.

If contains a 3-book, then every graph embeds into .

###### Proof.

Let be a graph. We first draw , possibly with crossings, in general position in the interior of a closed disk . Let be a simple curve in  with endpoints on and passing through all crossing points of the drawing of . By perturbing , we can ensure that, in the neighborhood of each crossing point of that drawing, coincides with the image of one of the two edges involved in the crossing. See Figure 1, left.

Let be a closed disk disjoint from . We attach to  by identifying with a part of the boundary of . Now, in the neighborhood of each crossing of the drawing of , we push inside  the part of the edge coinciding with , keeping its endpoints fixed. See Figure 1, right. This removes the crossings.

So embeds in the topological space obtained from  by attaching a part of the boundary of  along . But this space embeds in , because contains a 3-book. ∎

## 4 Reduction to EEPs on a pure 2-complex

Our next task is to reduce the problem Embed to a problem on a pure 2-dimensional complex. More precisely, let EEP-Sing be the problem EEP, restricted to instances where: is a pure 2-complex containing no 3-books; is a set of vertices of ; and is an injective map from to the nodes of  such that contains all singular nodes of . In this section, we prove the following result.

###### Proposition .

Any instance of Embed reduces to instances of EEP-Sing.

First, a definition. Consider a map , where is a set of nodes in  containing all singular nodes of . We say that an embedding  of  respects  if, for each , the following holds: If , then is not in the image of ; otherwise, .

In this section, we will need the following intermediate problem:

Embed-Resp:
Input: A graph  with vertices and edges, a 2-complex  (not necessarily pure) containing no 3-books, with simplices, and a map  as above, with domain of size .
Question: Does have an embedding into  respecting ?

Any instance of Embed reduces to instances of
Embed-Resp.

###### Proof.

By Proposition 3.1, we can without loss of generality assume that contains no 3-books. Let be the graph obtained from by subdividing each edge  times, where is the number of singular nodes of . We claim that has an embedding into  if and only if has an embedding  into  such that each singular node of  in the image of  is the image of a vertex of .

Indeed, assume that has an embedding  on . Each time an edge of  is mapped, under , to a singular node  of , we subdivide this edge and map this new vertex to ; the image of the embedding is unchanged. This ensures that only vertices are mapped to singular nodes. Moreover, there were at most subdivisions, one per singular node. So, by further subdividing the edges until each original edge is subdivided times, we obtain an embedding of  to  such that only vertices are mapped on singular nodes. The reverse implication is obvious: If has an embedding into , then so has . This proves the claim.

To conclude, for each map from the set of singular vertices of  to , we solve the problem whether has an embedding on  respecting . The graph  embeds on  if and only if the outcome is positive for at least one such map . By construction, there are at most such maps, because has size at most . ∎

Embed-Resp reduces to EEP-Sing.

###### Proof.

The proof is a bit long, and we refer to Appendix A, but the idea is simple: Because we restrict ourselves to embeddings that respect , and thus specify which vertex of  is mapped to each of the singular nodes of , what happens on the isolated segments of  is essentially determined. ∎

Before giving the proof, we first note:

###### Proof of Proposition 4.

It follows immediately from Lemmas 4 and 4. ∎

## 5 Reduction to an EEP on a possibly disconnected surface

The previous section led us to an embedding extension problem in a pure 2-complex without 3-book where the images of some vertices are predetermined. Now, we show that solving such an EEP amounts to solving another EEP in which the complex is a surface.

Let EEP-Surf be the problem EEP, restricted to instances where the input complex is (homeomorphic to) a possibly disconnected triangulated surface without boundary (which we denote by  instead of , for clarity). To represent the embedding  in such an EEP instance , it will be convenient to use the fact that, in all our constructions below, the image of every connected component of  under  will intersect the 1-skeleton of  at least once, and finitely many times. (Note that may use some nodes of .) Consider the overlay of the triangulation of  and of , the union of the 1-skeleton of  and of the image of ; this overlay is the image of a graph on ; each of its edges is either a piece of the image of an edge of  or a piece of a segment of ; each of its vertices is the image of a vertex of  and/or a node of . By the assumption above on , this overlay is cellularly embedded on , and we can represent it by its combinatorial map [19, 10] (possibly on surfaces with boundary, since at intermediary steps of our construction we will have to consider such surfaces).

In this section, we prove the following proposition.

###### Proposition .

Any instance of EEP-Sing reduces to an instance of EEP-Surf.

We will first reduce the original EEP to an intermediary EEP on a surface with boundary.

Any instance of EEP-Sing reduces to an instance of EEP in which the considered 2-complex is a possibly disconnected surface with boundary.

###### Proof.

The key property that we will use is that, since is pure and contains no 3-books, each singular node is incident to cones and corners only.

Figure 2 illustrates the proof. Let be the instance of EEP-Sing. We first describe the construction of the instance on the possibly disconnected surface with boundary. Let be a singular node; we modify the complex in the neighborhood of  as follows. Let be the number of cones at  and be the number of corners at . We remove a small open neighborhood  of  from , in such a way that the boundary of  is a disjoint union of circles and arcs. We create a sphere  with boundary components. Finally, we attach each circle and arc to a different boundary component of , choosing an arbitrary orientation for each gluing; circles are attached to an entire boundary component of , while arcs cover only a part of a boundary component of . Doing this for every singular node , we obtain a surface (possibly disconnected, possibly with boundary), which we denote by .

We now define , , and  from , , and  (again, refer to Figure 2). Let be a singular node of  and the vertex of  mapped on  by . In (and thus also ), we add a set  of loops with vertex . Let be a point in the interior of ; in , we map to , and we map these loops on  in such a way that each loop encloses a different boundary component of  (thus, if we cut along these loops, we obtain annuli and one disk).

Finally, we add to  (and thus also to ) a set  of new edges, each connecting to a new vertex. In , each new vertex is mapped to the boundary component of  corresponding to a corner, but not on the corresponding arc.

Let us call and  the resulting graphs, and  the resulting embedding of . Note that, from the triangulation of  with simplices, we can easily obtain a triangulation of  with simplices, and that the image of each edge of  crosses edges of this triangulation.

There remains to prove that these two EEPs are equivalent; see Appendix B. ∎

We now deduce from the previous EEP the desired EEP on a surface without boundary. Any instance of EEP-Sing on a possibly disconnected surface with boundary reduces to an instance of EEP-Surf.

###### Proof.

(Figure 4, in Appendix, illustrates the proof.) Let be an instance of an EEP on a possibly disconnected surface with boundary. We first describe the construction of , the EEP instance on a possibly disconnected surface without boundary.

Let be obtained from  by gluing a disk along each boundary component. Let be a boundary component of . If maps at least one vertex to , then we add to (and thus also to ) a new vertex , which we connect, also by a new edge, to each of the vertices mapped to  by . We extend  by mapping vertex  and its incident edges inside . Let us call and  the resulting graphs, and  the resulting embedding of . For each vertex of  on a boundary component, we added to and at most one vertex and one edge. There remains to prove that these two EEPs are equivalent; see Appendix B. ∎

Finally:

###### Proof of Proposition 5.

It suffices to successively apply Lemmas 5 and 5. ∎

## 6 Reduction to a cellular EEP on a surface

Let EEP-Cell be the problem EEP, restricted to instances where is a surface and is cellularly embedded and intersects each connected component of .

In this section, we prove the following proposition.

###### Proposition .

Any instance of EEP-Surf reduces to instances of EEP-Cell.

As will be convenient also for the next section, we do not store an embedding  of a graph  on a surface  by its overlay with the triangulation, as was done in the previous section, but we forget the triangulation. In other words, we have to store the combinatorial map corresponding to , but taking into account the fact that is not necessary cellular: We need to store, for each face of the embedding, whether it is orientable or not, and a pointer to an edge of each of its boundary components (with some orientation information). Such a data structure is known under the name of extended combinatorial map [6, Section 2.2] (only orientable surfaces were considered there, but the data structure readily extends to non-orientable surfaces).

### 6.1 Reduction to connected surfaces

We first build intermediary EEPs over connected surfaces. Let EEP-Conn be the problem EEP, restricted to instances where is a surface (connected and without boundary) and intersects every connected component of .

Any instance of EEP-Surf reduces to instances of EEP-Conn. More precisely (and this is a fact that will be useful to prove that Embed is in NP, see Theorem 1.1), any instance of EEP-Surf is equivalent to the disjunction (OR) of instances, each of them being the conjunction (AND) of instances of EEP-Conn.

###### Sketch of proof.

See Appendix C for details. We can embed each connected component of  that is planar and disjoint from  anywhere. There remains connected components of  that are disjoint from . For each of these, we choose a vertex, and we guess in which face of  it belongs. We then know which connected component of the surface each connected component of  is mapped into. ∎

### 6.2 The induction

The strategy for the proof of Proposition 6 is as follows. For each EEP from the previous lemma, we will extend  to make it cellular, by adding either paths connecting two boundary components of a face of , or paths with endpoints on the same boundary component of a face of  in a way that the genus of the face decreases. We first define an invariant that will allow to prove that this process terminates.

Let be an embedding of a graph  on a surface . The cellularity defect of is the non-negative integer

 \definecolor[named]pgfstrokecolorrgb0,0,.7\pgfsys@color@rgb@stroke00.7\pgfsys@color@rgb@fill00.7% \emph{cd}(H,Π,S):=∑f face of Π% genus(f)+∑f face of Π(number of boundaries of % f−1).

Some obvious remarks: can contain isolated vertices; by convention, each of them counts as a boundary component of the face of  it lies in. With this convention, every face of  has at least one boundary component, except in the very trivial case where is empty. This implies that is a cellular embedding if and only if .

The following lemma reduces an EEP to EEPs with a smaller cellularity defect. Any instance of EEP-Conn reduces to instances
of EEP-Conn where .

The reduction does not depend on the size of ; furthermore, the new graph  is obtained from the old one by adding exactly one edge and no vertex.

Admitting Lemma 6.2, the proof of Proposition 6 is straightforward:

###### Proof of Proposition 6.

We first apply Lemma 6.1, obtaining instances of EEP-Conn. To each of these EEPs, we apply recursively Lemma 6.2 until we obtain cellular EEPs. The cellularity defect of the initial instance is , being at most the genus of plus , because each boundary component of a face of  is incident to at least one edge of  (and each edge accounts for at most two boundary components in this way) or to one isolated vertex of . Thus, the number of instances of EEP-Cell at the bottom of the recursion tree is , in which the size of the graph is and the surface has at most simplices. ∎

### 6.3 Proof of Lemma 6.2

There remains to prove Lemma 6.2. The proof uses some standard notions in surface topology, homotopy, and homology; we refer to textbooks and surveys [25, 29, 5]. We only consider homology with coefficients.

Let be a surface with a single boundary component and let be a path with endpoints on the boundary of . If we contract this boundary component to a single point, the path  becomes a loop, which can be null-homologous or non-null-homologous. We employ the same adjectives null-homologous and non-null-homologous for the path . Recall that, if is simple, it separates  if and only if it is null-homologous. The reversal of a path  is denoted by . The concatenation of two paths and  is denoted by .

Let be a surface with boundary, let be a point in the interior of , and let , , and  be points on the boundary of . For each , let be a path connecting to . Let , , and . Let be a possible property of the paths , among the following ones:

• “the endpoints of  lie on the same boundary component of ”;

• is null-homologous” (if has a single boundary component).

Then the following holds: If both and  have property , then so does .

###### Proof.

This is a variant on the 3-path condition from Mohar and Thomassen [25, Section 4.3]. The first item is immediate. The second one follows from the fact that homology is an algebraic condition: The concatenation of two null-homologous paths is null-homologous, and removing subpaths of the form from a path does not affect homology. ∎

###### Proof of Lemma 6.2.

Since , there must be a face  of  with either (1) several boundary components, or (2) a single boundary component but positive genus. We will consider each of these cases separately, but first introduce some common terminology.

Let be an arbitrary spanning forest of  rooted at . This means that is a subgraph of that is a forest with vertex set such that each connected component of  contains exactly one vertex of , its root. The algorithm starts by computing an arbitrary such forest  in linear time.

For each vertex  of , let be the unique root in the same connected component of  as , and let be the unique path connecting to . If and  are two vertices of , let be the graph obtained from  by adding one edge, denoted , connecting and . (This may be a parallel edge if and  were already adjacent in , but in such a situation when we talk about edge we always mean the new edge.) Let be the unique path between and  in  that is the concatenation of , edge , and .

Case 1: has several boundary components.

Assume that has a solution . We claim that, for some vertices and  of , the embedding  extends to an embedding of  in which the image of the path lies in  and connects two distinct boundary components of .

Indeed, let be a curve drawn in  connecting two different boundary components of . We can assume that it intersects the boundary of  exactly at its endpoints, at vertices of . We can deform  so that it intersects  only at the images of vertices, and never in the relative interior of an edge. We can, moreover, assume that is simple (except perhaps that its endpoints coincide on ). Let be the vertices of  encountered by , in this order. We denote by the part of  between vertices and . We claim that, for some , we have that connects two different boundary components of : Otherwise, by induction on , applying the first case of Lemma 6.3 to the three paths , , and , we would have that, for each , has its endpoints on the same boundary component of , which is a contradiction for (for which the curve is ). So let be such that connects two different boundary components of ; letting and , and embedding edge as , gives the desired embedding of . This proves the claim.

The strategy now is to guess the vertices and  and the way the path is drawn in , and to solve a set of EEPs where is chosen as an appropriate extension of . Let us first assume that is orientable. One subtlety is that, given and , there can be several essentially different ways of embedding inside , if there is more than one occurrence of and  on the boundary of . So we reduce our EEP to the following set of EEPs: For each choice of vertices and  of , and each occurrence of  and  on the boundary of , we consider the EEP where extends and maps to an arbitrary path in  connecting the chosen occurrences of and  on the boundary of .

It is clear that, if one of these new EEPs has a solution, the original EEP has a solution. Conversely, let us assume that the original EEP has a solution; we now prove that one of these new EEPs has a solution. By our claim above, for some choice of and , some EEP has a solution, for some mapping inside  and connecting different boundary components of . In that mapping, connects two occurrences of and  inside . We prove that, for these choices of occurrences of and , the corresponding EEP described in the previous paragraph, , has a solution as well. These two EEPs are the same except that the path may be drawn differently in and , although they connect the same occurrences of and  on the boundary of . Under , the face  is transformed into a face  that has the same genus and orientability character as , but one boundary component less. The same holds, of course, for . Moreover, the ordering of the vertices on the boundary components of the new face is the same in and . Thus, there is a homeomorphism  of  that keeps the boundary of  fixed pointwise and such that . This homeomorphism, extended to the identity outside , maps any solution of to a solution of , as desired.

It also follows from the previous paragraph that the cellularity defect decreases by one. To conclude this case, we note that the number of new EEPs is : indeed, there are possibilities for the choice of (or ), and possibilities for the choice of the occurrence of (or ) on the boundary of .

If is non-orientable, the same argument works, except that there are two possibilities for the cyclic ordering of the vertices along the new boundary component of the new face: If we walk along one of the boundary components of  (in an arbitrary direction), use , and walk along the other boundary component of , we do not know in which direction this second boundary component is visited. So we actually need to consider two EEPs for each choice of , , and occurrences of and , instead of one. The rest is unchanged.

Case 2: has a single boundary component and positive genus. The proof is very similar to the previous case, the main difference being that, instead of paths in  connecting different boundary components of , we now consider paths in  that are non-null-homologous. See Appendix C.∎

## 7 Solving a cellular EEP on a surface

###### Proposition .

There is a function such that every instance of EEP-Cell can be solved in time .

###### Proof.

This is essentially the main result of Mohar [24]. The algorithm in [24] makes reductions to even more specific EEPs, and one feature that is needed for bounding the number of new instances is that the embedded subgraph  satisfies some connectivity assumptions. Our Appendix D provides more details. ∎

## 8 Proof of Theorems 1.1 and 1.2

We can finally prove our main theorems. First, let us prove that we have an algorithm with complexity :

###### Proof of Theorem 1.2.

This immediately follows from Propositions 3.1, 4, 5, 6, and 7. See Appendix E for details.∎

Finally, we prove that the Embed problem is NP-complete:

###### Proof of Theorem 1.1.

We give a detailed proof in Appendix E. The problem Embed is NP-hard because deciding whether an input graph embeds into an input surface is NP-hard [30]. It is in NP because (assuming contains no 3-books), a certificate that an instance is positive is given by a certificate that some instance of EEP-Surf is positive (see the proof of Proposition 5). Such an instance has a certificate, given by the combinatorial map of a supergraph of  cellularly embedded on  (see Section 6), that can be checked in polynomial time. ∎

## References

• [1] Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, and Ignaz Rutter. Testing planarity of partially embedded graphs. ACM Transactions on Algorithms (TALG), 11(4):32, 2015.
• [2] Dan Archdeacon. Topological graph theory. A survey. Congressus Numerantium, 115:5–54, 1996.
• [3] William W. Boone. The word problem. Annals of Mathematics, 70:207–265, 1959.
• [4] Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension. SIAM Journal on Computing, 43(5):1728–1780, 2014.
• [5] Éric Colin de Verdière. Computational topology of graphs on surfaces. In Jacob E. Goodman, Joseph O’Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, chapter 23. CRC Press LLC, third edition, 2018. See http://www.arxiv.org/abs/1702.05358.
• [6] Éric Colin de Verdière and Arnaud de Mesmay. Testing graph isotopy on surfaces. Discrete & Computational Geometry, 51(1):171–206, 2014.
• [7] Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari. Algorithms for planar graphs and beyond, 2011. Course notes available at http://courses.csail.mit.edu/6.889/fall11/lectures/.
• [8] Tamal K. Dey, Herbert Edelsbrunner, and Sumanta Guha. Computational topology. In Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors, Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, number 223 in Contemporary Mathematics, pages 109–143. AMS, 1999.
• [9] Tamal K. Dey and Sumanta Guha. Transforming curves on surfaces. Journal of Computer and System Sciences, 58:297–325, 1999.
• [10] David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599–608, 2003.
• [11] Jeff Erickson. Combinatorial optimization of cycles and bases. In Afra Zomorodian, editor, Computational topology, Proceedings of Symposia in Applied Mathematics. AMS, 2012.
• [12] Jeff Erickson and Kim Whittlesey. Transforming curves on surfaces redux. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1646–1655, 2013.
• [13] John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549–568, 1974.
• [14] Martin Juvan, Jože Marinček, and Bojan Mohar. Elimination of local bridges. Mathematica Slovaca, 47:85–92, 1997.
• [15] Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 771–780, 2008.
• [16] Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 382–390, 2007.
• [17] Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. arXiv:1706.04065, 2017.
• [18] Francis Lazarus and Julien Rivaud. On the homotopy test on surfaces. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 440–449, 2012.
• [19] Sóstenes Lins. Graph-encoded maps. Journal of Combinatorial Theory, Series B, 32:171–181, 1982.
• [20] Seth M. Malitz. Genus graphs have pagenumber . Journal of Algorithms, 17:85–109, 1994.
• [21] Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner. Embeddability in the 3-sphere is decidable. Journal of the ACM, 2018. To appear. Preliminary version in Symposium on Computational Geometry 2014.
• [22] Jiří Matoušek, Martin Tancer, and Uli Wagner. Hardness of embedding simplicial complexes in . Journal of the European Mathematical Society, 13(2):259–295, 2011.
• [23] Bojan Mohar. On the minimal genus of 2-complexes. Journal of Graph Theory, 24(3):281–290, 1997.
• [24] Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics, 12(1):6–26, 1999.
• [25] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.
• [26] Colm Ó Dúnlaing, Colum Watt, and David Wilkins. Homeomorphism of 2-complexes is equivalent to graph isomorphism. International Journal of Computational Geometry & Applications, 10:453–476, 2000.
• [27] Maurizio Patrignani. Planarity testing and embedding. In Roberto Tamassia, editor, Handbook of graph drawing and visualization. Chapman and Hall, 2006.
• [28] Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.
• [29] John Stillwell. Classical topology and combinatorial group theory. Springer-Verlag, New York, second edition, 1993.
• [30] Carsten Thomassen. The graph genus problem is NP-complete. Journal of Algorithms, 10(4):568–576, 1989.

## Appendix A Omitted proof from Section 4

###### Proof of Lemma 4.

Formally, we describe a set of transformations on , , and . The invariant is that they preserve the existence or non-existence of an embedding of  into  respecting .

Step 1.  We start by dissolving all the degree-two vertices of  that are not in the image of . (We recall that dissolving a degree-two vertex , incident to edges and , means removing and replacing and  with a single edge .) It is clear that the original graph  has an embedding on  respecting  if and only if the new graph (still called ) has an embedding on  respecting .

Step 2.  If a singular node is not used, then we can remove it without affecting the embeddability of . However, removing a vertex from a 2-complex does not yield a 2-complex. We thus define a 2-complex that has the same properties. Let be a singular node of a 2-complex . Let be the set of triangles and segments of  incident with , uniquely partitioned into , where each is either a cone, a corner, or an isolated segment. The withdrawal of from is the complex obtained by doing the following operation for each : We first create a new node , and then replace, in each triangle and edge of , the node  by .

For every singular node  of  such that and incident to at least two segments, we withdraw  from . For each created node , we let . The fact that embeds, or not, on  respecting  is preserved: Indeed, if embeds on the original complex respecting , then this corresponds to an embedding on the complex obtained by withdrawing , and avoiding the s, thus respecting ; conversely, if embeds on the complex obtained by withdrawing , respecting , then it avoids the s, and, after identifying together the s to a single point , this embedding avoids , and thus respects .

Step 3.  At this point, every singular node  with is incident to exactly one segment, and to no triangle. For each isolated segment of  such that and  are both different from , and contains an edge connecting and , we remove from  and remove from . We need to prove that this operation does not affect the (non-)existence of an embedding of  respecting . First, assume that, initially, there was an embedding  of  on  respecting ; then either segment is used by , in which case clearly there is still an embedding after this operation, or edge does not use segment  at all, in which case we can first modify  by embedding edge  on segment  and by moving the edges on  on the space where was before, so we are now in the previous case. Conversely, if after this operation has an embedding on  respecting , trivially it is also the case before.

Step 4.  For each isolated segment of  such that and  are both different from , but contains no edge connecting and , we do the following. In , we remove  and add a new segment where and  are new nodes; we also extend by letting . Finally, if contains at least one edge of the form , where has degree one and is not in the image of , we remove a single such edge; similarly, if it contains at least one edge of the form , where has degree one and is not in the image of , we remove a single such edge. This operation does not affect our invariant, for similar reasons; for example, if initially there was an embedding of  respecting , then segment  can only contain edges of  that are themselves connected components of , which we can re-embed on the new segment , or edges of the form or , where and  have degree one and are not in the image of .

Step 5.  For each isolated segment where is different from  but , we remove  from  and add a new segment where and  are new nodes; we also extend by letting . Finally, if contains at least one edge of the form , where has degree one and not in the image of , we remove a single such edge. The invariant is preserved, for reasons similar to the previous case.

Step 6.  Now, every segment of the complex (still called ) is incident to one or two triangles, except perhaps some segments that are themselves connected components of  and whose endpoints are not in the domain of . If there is at least one such segment, we remove all of them from , and remove all edges from  that are themselves connected components of  and such that and  are not in the image of ; as above, this does not affect whether embeds into  respecting .

Step 7.  Finally, for each node  of  incident to no segment, such that is different from , we do the following: If has degree zero, we remove  and ; otherwise, we immediately return that does not embed into  respecting . For each node  of  that is incident to no segment and such that , we remove , and remove a single degree-zero vertex of  not in the image of , if one exists.

Conclusion. Now, has no node that is itself a connected component; each of its segments is incident to one or two triangles. Also, maps each singular node of  to a vertex of . It may map some other nodes of  to , but such nodes are non-singular and, if an embedding uses them, a slight perturbation will avoid them, so we can remove the nodes  such that from the domain of  without affecting the result. Now, we have an EEP as specified in the statement of Proposition 4.

Finally, it is easy to check that, in each of the seven steps above, the numbers of vertices and edges of  do not increase, and the number of simplices of  increase by at most a multiplicative constant. Moreover, the domain of  also does not increase (it increases when we withdraw singular nodes, but the images of the new nodes are , and such nodes are later removed from the domain of ). ∎

## Appendix B Omitted proofs from Section 5

###### End of proof of Lemma 5.

There remains to prove that the two EEPs constructed are equivalent.

Let us first prove that any solution  of the EEP instance yields a solution of the EEP instance . Let be a singular node of , and let be the vertex of  mapped to . We need to modify locally in the neighorhood  of  that is removed when transforming to . Without loss of generality, up to an ambient isotopy of  that does not move , we can assume that the image of  intersects  exactly in straight line segments having  as one endpoint. To build a solution of , we first remove the part of  inside , and we reconnect  to each point of the image of  lying on the boundary of , by paths on ; this is certainly possible because each point of  not in the image of can be connected to  by a path that does not meet (except at ). Thus, has a solution.

Conversely, let be a solution of the EEP ; we build a solution of . As above, let be a point of  that was obtained from a singular node  of . We now show that we can assume that does not enter , except for , , , and the edges in  incident to :

First, the part of  lying in the connected component  of  minus the image of  that is a disk corresponds to a planar subgraph of , connected to the rest of  by  only; we can re-embed this planar subgraph of  in . Next, consider a cone at . The part of  enclosed by the corresponding loop of  is an annulus; the situation is as on Figure 3, top, and, by an ambient isotopy of , we can push the part of  that lies in the annulus outside it, except for those edges touching . Finally, consider a corner at , and the annulus that is the part of  enclosed by the corresponding loop in . The local picture for this part of  is as shown on Figure 3, bottom, and similarly by an ambient isotopy of  we can push the part of  on  outside it, except for those edges touching .

Now, a solution of can be obtained by the following procedure, for each of the singular nodes : (1) Remove the sphere , together with the image of  inside ; (2) add the neighborhood  of ; (3) reconnect to  the points on the image of  that lie on the boundary of . ∎

###### End of proof of Lemma 5.

Clearly, any solution of yields a solution of
. Conversely, let  be a solution of ; we build a solution of . Let be a boundary of . There are two cases:

• If no vertex of is mapped to , then maps  outside the closure of , so, by an ambient isotopy of  that does not move , we can push  outside .

• Otherwise, the disk  is split into sectors by the edges incident to ; the image of  by  does not enter the interior of each sector, and intersects the boundary of a sector exactly along the image of  and of two edges incident to . Thus, by an ambient isotopy that keeps the image of  fixed, we can push the image of  out of each sector.

After doing this for every boundary component , we obtain that the restriction of  to  is a solution of . ∎

## Appendix C Omitted proofs from Section 6

###### Proof of Lemma 6.1.

We start by removing the connected components of  that are planar and disjoint from . (Testing planarity takes linear time [13].) This does not change the solution of the EEP, because such connected components can be embedded on an arbitrarily small planar portion of  (provided is non-empty, but otherwise the original EEP-Surf instance can be solved trivially). So without loss of generality, every connected component of  disjoint from  is non-planar. Let be an arbitrary set of vertices, one per non-planar connected component of  disjoint from . Without loss of generality, the number of vertices in  is at most the genus of , which is at most , because otherwise the initial EEP has no solution.

Let ; every connected component of  intersects . For each vertex of , we guess the face of  it has to be embedded in, and extend accordingly, by adding the images of  in ; let be the resulting embedding of . By the previous paragraph, the number of these guesses is at most . It is clear that the initial EEP has a solution if and only if one of these EEPs has a solution.

These EEPs are almost of the form announced in the lemma, except that can be disconnected. However, in any solution of this EEP, we know the connected component of  each connected component of  has to embed in, because each connected component of  intersects . We can thus reformulate the EEP as the conjunction of several EEPs, one per connected component of . (Of course, we can discard the connected components of  disjoint from .) ∎

###### End of proof of Lemma 6.2.

There remains to prove Case 2: has a single boundary component and positive genus.

The proof is very similar to Case 1, the main difference being that, instead of paths in  connecting different boundary components of , we now consider paths in  that are non-null-homologous (if is orientable) or one-sided (if is non-orientable). For brevity we call such paths essential. Observe that Lemma 6.3 is similarly valid for the property “ is one-sided” (if has a single boundary component).

Assume that has a solution . We claim that, for some vertices and  of , the embedding  extends to an embedding of  in which the image of the path lies in  and is essential. The proof is similar in spirit to the corresponding claim in Case 1: We let be an essential curve in  intersecting the boundary of  exactly at its endpoints; we can assume similarly that it is simple and intersects only vertices of , in the order . For some , must be essential, by induction and by Lemma 6.3; this gives an embedding of .

If is orientable, we reduce the original EEP to the following set of EEPs: For each choice of vertices and  of , and each occurrence of and  on the boundary of , we consider the EEP where extends  and maps to an arbitrary path  in  connecting the chosen occurrences of  and  on the boundary of  in such a way that is non-null-homologous. As before, the only subtlety is to prove that, if we have two EEPs and such that are not embedded exactly in the same way in and , but are non-null-homologous in  and connect the same occurrences of  and  on the boundary of , then these EEPs are equivalent. This follows from the fact that the image of in  cuts  into a face that is an orientable surface with two boundary components and with (Euler) genus that of  minus two (because is non-null-homologous in both embeddings, and thus non-separating in both cases). Moreover, the ordering of the vertices along the boundary components of the new face is the same in both and . Thus, as before, there is a homeomorphism  of  that keeps the boundary of  fixed pointwise and such that , which similarly concludes. It also follows that the cellularity defect decreases by two. The number of these new EEPs is, similarly, .

If is non-orientable and the genus of  is either one or even, then by Euler’s formula, a similar argument can be used: Regardless of the way we draw as a path connecting the chosen occurrences of and  on the boundary of  in such a way that is one-sided, cutting along  results in a surface whose topology is uniquely determined (it is a disk if the genus of  is one, and a non-orientable surface with genus that of  minus one, if the genus of  is even). Moreover, the ordering of the vertices along the boundary of the new face is uniquely determined. The cellularity defect decreases by one, and the same argument as above concludes.

Finally, if

is non-orientable and its genus is odd and at least three

, then cutting  along such a one-sided path  results in a surface in which the ordering of the vertices along the single boundary component is uniquely determined, but this surface, with genus that of  minus one, can be orientable or not. Thus, for each choice of vertices and  of , and each occurrence of and  on the boundary of , we actually need to consider two EEPs, one in which is mapped to a path that cuts  into an orientable surface, and one in which is mapped to a path that cuts  into a non-orientable surface. The rest of the argument is unchanged. ∎

## Appendix D Omitted proof from Section 7

When solving EEPs on surfaces, a useful property of the embedded subgraph is the following one. We say that a subgraph  of  has property (E) if has no local bridges. This means that every path of , all of whose vertices have degree at most two in , is an induced path in , and every connected component of is adjacent to a vertex in . In fact, what we need is a weaker version of property (E) where we first prescribe a subset  of vertices of , where contains all vertices whose degree in  is different from two, and possibly a constant number of vertices whose degree in  is equal to two. Then we say that has property (E) with respect to  if the above property holds for every path  that is disjoint from .

###### Proof of Proposition 7.

This is essentially the main result from [24]. The algorithm from [24] first reduces the problem to an instance such that satisfies property (E) with respect to a subset that contains all vertices of  of degree different from two (all these are also vertices in  of degree different from two) plus a constant number of vertices of degree two in , where this constant number is bounded from above in terms of the genus of , which is itself bounded from above by . For this purpose, [24] relies on another paper [14]. After achieving this property, the paper [24] reduces the EEP to a constant number (where the constant depends on ) of “simple” extension problems [24, Section 4], which are then solved in [24, Theorem 5.4]. ∎

## Appendix E Omitted proofs from Section 8

###### End of proof of Theorem 1.2.

Consider an instance of Embed. Proposition 3.1 allows to discard the 2-complexes containing a 3-book. Proposition 4 reduces the problem to instances of EEP-Sing. Proposition 5 reduces each such instance into an instance of EEP-Surf. Proposition 6 reduces that instance into instances of EEP-Cell. Proposition 7 shows that each such instance can be solved in time . ∎

###### Proof of Theorem 1.1.

Let us first prove that the problem is NP-hard. The following problem Graph-Genus is NP-hard: Given a graph  and an integer , decide whether embeds on the orientable surface of genus  [30]. This almost immediately implies that Embed is NP-hard; the only subtlety is that in Graph-Genus, is specified in binary, thus more compactly than a triangulated surface of genus  (and thus triangles). To be very precise, given an instance of Graph-Genus, we transform it in polynomial time into an equivalent instance of Embed as follows: If has at most edges, then we transform it into a constant-size positive instance of Embed (every graph with edges embeds on the orientable surface of genus ); otherwise, we consider the instance where is a 2-complex that is an orientable surface of genus ; since has at least edges, the transformation takes polynomial time in the size of .

We now prove that the problem Embed belongs to NP. The case where contains a 3-book is trivial; let us assume that it is not the case. The proof of Proposition 5 shows that an Embed instance is positive if and only if at least one instance of EEP-Surf, among of them, is positive. The certificate indicates which of these instances is positive (this requires a polynomial number of bits), together with a certificate that this instance is indeed positive (see below). To check this certificate, the algorithm builds the corresponding instance of EEP-Surf (as done in Section 5—this takes polynomial time) and checks the certificate.

Here is a way to provide a certificate for an instance of EEP-Surf. In Section 6, we have proved that, if we have an instance of EEP-Surf, then there exists a cellular embedding  (in the form of a combinatorial map) of a graph  containing , and such that extends . Moreover, is obtained from  by adding a number of edges that is , where is the size of the original complex. (Recall that in the instance of EEP-Surf, the size of  is .) The cellular embedding  of , given as a combinatorial map, is the certificate that is positive: Given and this certificate, we can in polynomial time check that contains , that the restriction of  to  is indeed , and that the combinatorial map of  is indeed an embedding on . ∎


text:
# Fourier Series of Triangular waveform

Fourier Series of Triangular waveform

this is the solution of Fourier series of a triangular waveform from the book Circuits and Networks: Analysis and Synthesis by Shyammohan S. Palli. In this problem they have take the time period of the triangular waveform from -π to +π instead of 0 to 2π.

Now, from -π to 0 the equation of the waveform is as shown below

and from 0 to +π the equation of the waveform is

Which gives

My question is,

If i take the interval from 0 to 2π.then from 0 to +π the equation of the waveform will be

and from +π to +2π the equation of the waveform will be

But this gives

which did not match with previous.My question is why they took the interval from -π to +π instead of 0 to 2π.

I will post my calculation here

• Without seeing your actual solution, the result should be the same. Taking the interval as $[0, 2\pi]$, the average value is: $$a_0 = \frac{1}{2\pi}\int_0^{2\pi}\nu(t)\mathrm{d}t=\frac{1}{2\pi}\int_0^{\pi}\ \left(10 - \frac{10}{\pi}t\right)\mathrm{d}t + \frac{1}{2\pi}\int_{\pi}^{2\pi}\ \left(\frac{10}{\pi}t - 10\right)\mathrm{d}t=5$$ – Winter Soldier Feb 13 at 16:20


text:
# Trace class operators

I have a question concerning the definition of the square root of bounded linear operators. To introduce some notation: tr denotes the trace of linear operators and $\mathcal{L}(H)$ denotes the set of bounded linear operators, from H to H, where H symbolizes a Hilbert space. L' stands for the adjoint operator of L. We introduced the the space of trace class operators in the following way: $\{L \in \mathcal{L}(H) \ : \ tr((LL')^{\frac{1}{2}} < \infty \}$. The problem is, that I don't know how how square root of the above mentioned operator is defined.

Notice that $LL'$ is positive definite. Square root is well-defined for bounded, positive definite operators (by functional calculus theorems).
• I only read, what you have stated, but I can't actually imagine, what a quare root in the context of Hilbert spaces means, e.g. how to 'calculate' $Q^{\frac{1}{2}} h$ for an $h \in H$. – David Jan 11 '13 at 13:37
• @David: for $\lvert x\rvert\leq 1$ we have $\sqrt{1-x}=1+\sum_{n=1}^\infty \binom {1/2} n (-x)^n$ (and the convergence is uniform). Using this series expansion you can define square root for positive operators $Q$ of norm not greater than $1$, and for others you can put $\sqrt Q= \sqrt {Q/\lVert Q\rVert }\cdot \sqrt {\lVert Q\rVert}$. For more detailed discussion, I suggest you check some functional analysis textbook. It should be explained in detail in proximity of polar decomposition of bounded operators. – tomasz Jan 11 '13 at 13:57
It is a well-known fact that every bounded positive operator on a Hilbert space (which are exactly those of the form $LL'$ for some bounded $L$) has a unique positive square root. This is a consequence of the continuous functional calculus; you can find about in any Functional Analysis book that talks about C$^*$-algebras.


text:
# 3. Find the height of a cuboid whose base area is 180 cm 2 and volume is 900 cm 3?

Given that the height of a cuboid whose base area is $180cm^2$ and volume is $900cm^3$;
As $Volume\ of\ cuboid = Base\ area\times height$
So, we have relation: $900cm^3= 180cm^2\times height$


text:
# Changeset 964:7fdaa05a69a1 in lemon-1.2 for lemon/circulation.h

Ignore:
Timestamp:
09/13/12 11:56:19 (7 years ago)
Branch:
default
Parents:
961:4bb9e72e1a41 (diff), 963:761fe0846f49 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #449 to branches >=1.2

Files:
2 edited

### Legend:

Unmodified
 r963 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \brief The type of supply map. /// /// The type of the map that stores the signed supply values of the /// nodes. /// The type of the map that stores the signed supply values of the /// nodes. /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef SM SupplyMap; /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept. #ifdef DOXYGEN typedef GR::ArcMap FlowMap; #else typedef typename Digraph::template ArcMap FlowMap; #endif /// \brief Instantiates a FlowMap. /// The elevator type used by the algorithm. /// /// \sa Elevator /// \sa LinkedElevator /// \sa Elevator, LinkedElevator #ifdef DOXYGEN typedef lemon::Elevator Elevator; #else typedef lemon::Elevator Elevator; #endif /// \brief Instantiates an Elevator. \geq sup(u) \quad \forall u\in V, \f] \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or negative in order to have a feasible solution (since the sum constraints have to be satisfied with equality, i.e. all demands have to be satisfied and all supplies have to be used. If you need the opposite inequalities in the supply/demand constraints (i.e. the total demand is less than the total supply and all the demands \tparam SM The type of the supply map. The default map type is \ref concepts::Digraph::NodeMap "GR::NodeMap". \tparam TR The traits class that defines various types used by the algorithm. By default, it is \ref CirculationDefaultTraits "CirculationDefaultTraits". In most cases, this parameter should not be set directly, consider to use the named template parameters instead. */ #ifdef DOXYGEN /// able to automatically created by the algorithm (i.e. the /// digraph and the maximum level should be passed to it). /// However an external elevator object could also be passed to the /// However, an external elevator object could also be passed to the /// algorithm with the \ref elevator(Elevator&) "elevator()" function /// before calling \ref run() or \ref init(). /// \param graph The digraph the algorithm runs on. /// \param lower The lower bounds for the flow values on the arcs. /// \param upper The upper bounds (capacities) for the flow values /// \param upper The upper bounds (capacities) for the flow values /// on the arcs. /// \param supply The signed supply values of the nodes. } /// \brief Sets the tolerance used by algorithm. /// /// Sets the tolerance used by algorithm. /// \brief Sets the tolerance used by the algorithm. /// /// Sets the tolerance object used by the algorithm. /// \return (*this) Circulation& tolerance(const Tolerance& tolerance) { _tol = tolerance; /// \brief Returns a const reference to the tolerance. /// /// Returns a const reference to the tolerance. /// Returns a const reference to the tolerance object used by /// the algorithm. const Tolerance& tolerance() const { return _tol; /// \name Execution Control /// The simplest way to execute the algorithm is to call \ref run().\n /// If you need more control on the initial solution or the execution, /// first you have to call one of the \ref init() functions, then /// If you need better control on the initial solution or the execution, /// you have to call one of the \ref init() functions first, then /// the \ref start() function.


text:
# How does a planet's gravity push away smaller bodies that would otherwise intersect its orbit?

I was reading an article about dwarf planets online where I stumbled upon the following definition of a planet:

The International Astronomical Union defines a planet as being in orbit around the sun, has enough gravity to pull its mass into a rounded shape (hydrostatic equilibrium), and has cleared its orbit of other, smaller objects.

The article put a lot of emphasis on the last line, but given that gravity is an attractive force, how do big planets push away smaller objects from their orbit that would otherwise intersect it?

The article I read: https://www.space.com/amp/15216-dwarf-planets-facts-solar-system-sdcmp.html

• Clearing its orbit of other objects does not require pushing them away. A small object may just crash into the planet. It happened many times on Earth during the last billions of years. – Uwe May 4 '20 at 7:36
• Ideally they crash into other planets. We got to see Jupiter do its job with the impact of Shoemaker–Levy 9. (my answer at WB for, minimum set of physical characteristics to define an Earth like planet) – Mazura May 4 '20 at 22:10
• @Uwe The Moon is witness to one such event. – Peter - Reinstate Monica May 5 '20 at 8:08
• @eagle275: And of course that artificial (and false: no planet has actually "cleared its orbit") was made up entirely so some people would have reason to claim that Pluto was not a planet. – jamesqf May 5 '20 at 16:43
• @AtmosphericPrisonEscape It's not that hard to hit a planet, just have half your team work in metric :) – Harper - Reinstate Monica May 5 '20 at 19:51

I feel the need to correct some issues that were brought up in the other answers.

Yes, gravity is an attraction-only force.
But due to its relative weakness, objects in space can attain large velocities, before getting the chance to collide with any single target. In physics we would speak of excess angular momentum, which is hard to get rid of in space, but I will try to avoid that terminology here.
What 'large velocity' means, can be expressed in terms of comparing the vectorial velocity of a body $$\vec v$$, with respect to a potential target, and the scalar escape velocity of that potential target $$v_{\rm esc}$$.

If $$|\vec v|>v_{\rm esc}$$, and orbits intersect, then one can think of our body experiencing only a slight deviation from its initial path due to the target's gravity, and the collision probability is given by the geometric cross-section of the target, which is always small, even for stars. This is in fact the normal case in the solar system, as opposed to what other, wrong, answers were presenting.

If $$|\vec v|\approx v_{\rm esc}$$, and the objects are nearly co-orbital, then it is hard to intersect the orbits and the body will end up mostly on a horseshoe-orbit around the target or be ejected, see also a thorough discussion of this case in the fantastic "Solar System Dynamics" by Murray & Dermott.

If $$|\vec v|, and orbits intersect, then the usual outcome is that the object is captured on an eccentric orbit around the target as a satellite. Again, a collision is extremely improbable, because the range of velocities in space is just enormous. To exactly hit the target object and not miss it, the velocity has to be fine-tuned to a very small range of values.

Synthesizing all this, we can say
Intersection of orbits does not imply collisions. In the overwhelming majority of cases orbit clearing works via swing-bys and not via accretion onto the clearing planet.

Furthermore, the popular picture of planet growth via collisions is that the young protoplanet gets bombarded a lot via asteroids and comets and thus grows. This picture seems to be broadly correct (e.g. Raymond et al. (2006), Alibert et al. (2018)), but with the caveat as stated above: This process is extremely inefficient, and most asteroids/comets will miss the young protoplanet. This is what makes planet formation with large impactors hard, and in modern times alternatives with gas-assisted drag of much smaller solids are considered (e.g. Morbidelli et al. (2015)) in order to build the terrestrial planets in the solar system.

• In the case of v << v_esc, isn't it more likely that the captured satellite will end up in an unstable orbit, which eventually will decay until the satellite impacts the planet? On planet-formation timescales this should happen most of the time, right? – KutuluMike May 5 '20 at 23:55
• @KutuluMike: No, the probabilities are ordered according to Miss > Hit > Unstable orbit. The capture into an unstable orbit is would require even more fine-tuned velocities, because you would need to end up in a orbit that grazes a thin atmospheric ring of several scale-heights thickness, which has still smaller geometric cross-section than the Earth. – AtmosphericPrisonEscape May 6 '20 at 9:38
• This is simply a more sophisticated way of saying that whilst frame-dragging might result in a collision, it usually accelerates the object out of orbit instead, if the object's approach velocity is greater than the planet's escape velocity. Assuming that the angle of approach is greater than zero. – Ed999 May 6 '20 at 13:16
• @Ed999 This has nothing to do with frame-draggin. This is pure Newtonian gravity. – AtmosphericPrisonEscape May 6 '20 at 13:27
• @KutuluMike: If you check en.wikipedia.org/wiki/Orbital_decay, then there is a document linked at the end that lists orbital decay rates for various satellites as function of altitude. There, I took the 'fast decay' curve, which is an exponential, fitted it, and checked at which altitude the decay time would be the age of the solar system (5.67 Gyrs). The result is an altitude of ~1200 km, which is about the altitude of the exobase, i.e. space space. Your chance encounter with small velocity must therefore get a perigee of < 1200km altitude for it to ever decay. This still has a small – AtmosphericPrisonEscape May 13 '20 at 19:41

There are two ways in which a massive orbiting body, such as a planet, can clear a smaller object from the vicinity of its orbit. One, obviously, is by colliding with it. The other, more common way is called the gravitational slingshot effect.*

This is a trick that many space probes have used to gain (or lose) extra speed and thus get further away from (or closer to) the sun, but it's also something that happens completely naturally.

Basically, when the smaller object passes close to the planet, the gravitational pull of the planet will cause the small object's path to curve.** Viewed from the planet's reference frame, the small object will follow an (approximately) hyperbolic fly-by trajectory, arriving and leaving at the same speed (relative to the planet) but in a different direction.

However, the planet is also in orbit around the sun, and thus moving relative to it. If the new direction in which the small object leaves the planet's vicinity after the encounter happens to point the same way as the planet is moving in its orbit, the object will end up moving in the same direction as the planet but faster, and will thus be flung outwards from the sun.

(Conversely, if the object leaves the planet's vicinity in the opposite direction to the way the planet is moving in its orbit relative to the sun, then the opposite velocities will (partially) cancel out and the object will end up losing speed and thus falling inwards towards the sun — possibly even into the sun, if it manages to lose enough velocity.)

To illustrate this visually — a picture often being worth a thousand words — here's a couple of screenshots from Kerbal Space Program. (Because why the heck not? KSP's orbital mechanics model is a bit simplified compared to real life — it basically follows the patched conic approximation — but it's quite sufficient for modeling gravitational slingshots.)

The first screenshot below shows a small asteroid — mysteriously labelled as "Unknown Object" on the map — that has fortuitously (or, rather, via shameless use of KSP's cheat menu) been captured into a temporary orbit around the planet Kerbin, KSP's Earth-analogue (shown as the dark blue sphere in the exact center of the map). The reason why the asteroid's current orbit (blue-green line) is only temporary*** is that it's quite close to the orbit of the larger of Kerbin's two moons, creatively named "The Mun", soon resulting in a near pass:

As the asteroid passes by the Mun (orange line), it ends up getting flung in (more or less) the same direction as the Mun is orbiting Kerbin, gaining a bunch of extra speed relative to Kerbin and, in fact, getting ejected from the Kerbin system entirely (purple line).

(In real life, the extra momentum gained by the asteroid would be balanced by a corresponding loss of momentum by the Mun, slowing it down very, very slightly. Since the Mun is much bigger than the asteroid, however, the slowdown is so negligible that KSP doesn't even try to model it.)

Meanwhile, here's the same close pass as seen from the Mun's viewpoint:

As you can see, in this reference frame the fly-by trajectory looks quite symmetric: the asteroid falls towards the Mun (but not so directly that it would crash into it), accelerating as it's pulled closer by the Mun's gravity, and then starts slowing down again after passing the closest point of approach (marked as "periapsis" on the map). But the end result is that the asteroid leaves the Mun's vicinity in a different direction, and that change in direction is enough to put it into a completely different orbit around Kerbin — in this case, one that ends up taking it out of Kerbin's vicinity entirely. Thus the Mun has once again cleared its orbit of such pesky intruders.

*) There's a kind of a third way, too, where the planet and the smaller object end up in an orbital resonance that gradually transfers momentum from the planet to the small object without them ever getting very close to each other. You can sort of think of such a resonance like a series of very slight gravitational slingshots, each of which nudges the smaller object's orbit further and further in the same direction.

**) Obviously, the converse happens too, but if the smaller object is much smaller than the planet, then its effect on the planet's motion will be negligible.

***) It's actually quite natural for a captured asteroid to end up in such an unstable orbit: since orbital mechanics is time-symmetric, both in KSP and in real life, if we traced the asteroid's orbit backwards in time we'd presumably find another, earlier encounter with the Mun that would've caused it to be captured into its current temporary orbit in the first place. In real life, the Earth every once in a while also captures such temporary satellites, but their orbits are also basically never stable, since the same gravitational interactions that allowed them to be captured will also, by time symmetry, eventually allow them to escape again. (Of course, in this case I was actually lazy and just cheated the asteroid into that orbit, rather than waiting for one to be "naturally" captured.)

• +1 Nice illustration of the fly-by physics in the limit of similar velocities. Do you know what orbital integrator KSP uses? Is it a simple leapfrog? – AtmosphericPrisonEscape May 5 '20 at 8:16
• @AtmosphericPrisonEscape: Even simpler, in a way; KSP splits the orbit into a series of conic (elliptic / parabolic / hyperbolic) segments and solves those analytically, gluing the results together. Hence the term "patched conic approximation". (I'm not sure how it's solving for orbital encounters to find the patch points; there might be some clever math involved there.) – Ilmari Karonen May 5 '20 at 8:23
• @AtmosphericPrisonEscape: see wiki.kerbalspaceprogram.com/wiki/Sphere_of_influence for an explanation. There is a mod for the game, Principia, that does implement n-body physics (github.com/mockingbirdnest/Principia/blob/master/README.md). – Roel Schroeven May 5 '20 at 12:26
• @RoelSchroeven: Thank you. So do I understand this correctly, that KSP never solves the n-body problem, but instead, when a satellite leaves the SOI of Earth, then it orbits on a 1-body solution in the SOI of the sun? – AtmosphericPrisonEscape May 5 '20 at 16:51
• @AtmosphericPrisonEscape: Yes, until it comes close enough to the Earth or some other planet to cross into its SOI. – Ilmari Karonen May 5 '20 at 16:53

Gravity does not push away, it only attracts. What clearing means in this case is that a planetary body attracts smaller objects to it. This will end up with one of the following effects:

1. The object will impact the surface larger object or burn up in its atmosphere, presuming it has one. This is how many planets gain mass earlier on in their development, i.e. they get hit a lot for a long time until the orbit is cleared of debris, then things settle down
2. The smaller object will go into orbit of the larger object, and become a moon. This is infrequent
3. The small object will be thrown into a radically different orbit by the larger object's gravity, which clears it out of the larger object's path in the future
• Isn't giving a small body a slingshot with a close encounter and ejecting it from the solar system also "clearing its orbit"? Some theories suggest Jupiter or Saturn might have ejected another planet. – Polygnome May 4 '20 at 8:13
• Good point, see my edit @Polygnome – GdD May 4 '20 at 8:23
• Yeah, and that's by far the more important mechanism. Collisions are really unlikely because “space is big”™ and frictionless. It's true that planets originally accreted lots of material, but that was in the protoplanetary disk, which had so much stuff flying around in it that inelastic collisions in between the smaller objects created effectively a sink for kinetic energy. When an object does collide with a planet, like Shoemaker-Levy 9, it's typically not a direct collision but first getting below the Roche limit, “inelastically disintegrating”, and the parts then crashing down. – leftaroundabout May 5 '20 at 15:38
• Ilmari Karonen appears to have given a convincing explanation of how gravity does push objects away, at least in cases in which the object pushed away has a trivial mass in comparison to that of the body causing the gravity. The "push" is accounted for by the acceleration imparted to the smaller object by the rotation-dragging principle. – Ed999 May 6 '20 at 12:57
• Sorry @Ed999, gravity does not push. There are mechanisms which end up with smaller body moving away from larger body after their interaction, but gravity does not push. – GdD May 6 '20 at 13:43

We can assume as if they would exchange kinetic energy randomly. I.e. in the general case, depending on the circumstances, both bodies can gain and lose kinetical energy.

However, for the smaller body, gaining or losing the same kinetic energy means a larger change in its velocity. The orbits depend on the velocities and not on the energy (remember, both are in the gravitational field of a body being much larger than both of them).

The result is that the orbit of the smaller body will be affected more by the same change, thus it will go away from the orbit of the larger body and not vice versa.

• This is unclear. Can you give it another shot, perhaps with diagrams? BTW, no such animal as "kinetical" – Carl Witthoft May 4 '20 at 14:15
• @CarlWitthoft Kinetic fixed, sorry. What is not clear? If there is a random elastic collision between a big and a small body in the gravitational field of an object far more massive than both of them, then the small one will go away. This is what I tried to explain. – peterh May 4 '20 at 14:33

Put simply, the planet (P) doesn't push away an intruder (i) like so:

Rather it pulls the intruder like so:

All intruders sharing the planet's orbit will generally be traveling parallel to the planet previous to the encounter. Therefore, assuming the intruder is not heading perfectly for the planet's center of mass (whereby it would impact the planet anyway), the pull of the planet's gravity will add momentum that is pointed in a direction other than that of the original orbit (in addition to momentum in the original orbital direction but this is irrelevant).

No matter which way the intruder passes the planet (or the planet passes it), it will end up with additional momentum that is perpendicular to the planet's orbit, yanking it out of that orbit.

• I very much wanted to up-vote, but there was a snag: if two objects share the same orbit (All intruders sharing the planet's orbit), they must, by definition, have identical velocity. Therefore, on the most obvious level, one will not catch-up with the other. There may be infinite complexities introduced by the mass of external objects: but the basic principle has to be that a body in a stable orbit has a stable velocity. – Ed999 May 6 '20 at 13:06
• "the same orbit" is used in the context of "a body must clear its orbit to be a planet". This refers to a general orbital volume (much larger in cross-section than the cross-section of the body), not a perfect line defined by the body's center of mass – johnDanger May 6 '20 at 15:37
• If you are modifying your explanation in that manner, then it seems that objects with a smaller orbital radius than the planet will be travelling faster than it, so will catch up to it, whereas those with a greater orbital radius will be travelling more slowly, so the planet will do the catching-up. How does this explain the more fundamental point: the gravity of any body having mass (i.e. Pluto) will tend to disrupt the orbital path of a body it encounters which has less mass. How does this equate to Pluto not clearing its orbit? It seems to be doing just what any planet does. – Ed999 May 6 '20 at 16:05
• It's not a modification, an answer is always in the context of the question. As to the rest of your question, yes any body with mass will have this effect on any body it encounters (whether it is larger or not) but only a planet is considered to have a dominant enough presence that it (and its satellites) will end up as the only significantly large body in that orbit (again with the orbit being a general volume) – johnDanger May 6 '20 at 16:23


text:
# Current density of a moving conductor or conducting fluid

1. Jan 11, 2010

### omyojj

I beg you to understand my poor Eng..
If there is any poor grammar or spelling..plz correct me..

While studying MHD with "An Introduction to Magnetohydrodynamics" written by Davidson,
I encountered the term 'current density'..
As you know well, empirically,
$$\mathbf{J} = \sigma \mathbf{E}$$
with electric field being measured in a frame of reference in which the charged test particle is at rest.

It says
I can't understand this "empirical" Ohm's law for moving conductor(or conducting fluid) because, to my knowledge, $$\mathbf{J}(\mathbf{r},t) = \rho_e(\mathbf{r},t)\mathbf{v}(\mathbf{r},t)$$ is thought to be the more fundamental definition of current density. It is basically a vector having the (net) direction of charged particles drift velocity..
But $$\mathbf{u} \times \mathbf{B}$$ clearly does not coincide in direction with $$\mathbf{u}$$..

Also, I'd like to raise a question about the e.m.f. generated by a relative movemnet of the imposed magnetic field and the moving fluid. Why is it of order $$|\mathbf{u} \times \mathbf{B}|$$? Does it come from Faraday's law?

2. Jan 13, 2010

### payumooli

I couldn't understand all your doubts

i will post some comments which may help

the current density vector $$\mathbf{J}(\mathbf{r},t)$$
need not be in the direction of u, it can be found in any direction. so u x B may not necessarily coincide with u.

may be in a wire the J is maximum in direction of u and it is of interest

the magnetic force component u x B is also responsible for genrating an emf. the equation used to arrive to this result should be faraday and maxwells equation.

i would like to read some material and give you a concrete explanation

3. Jan 13, 2010

### Bob S

In J = σ·E, σ is electrical conductance (ohm-m)-1.

In F = σ·V(E + v x B), σ is charge density (Coulombs per unit volume).

I think.

Bob S

4. Jan 14, 2010

### omyojj

suppose that the prescribed magnetic field $$\mathbf{B} = B_0 \hat{\mathbf{z}}$$ is present..and suppose that ,at time t, at the origin of the inertial frame, a particle with charge q moves along the y-direction with velocity u..then the Lorentz force due to magnetic field is in the x-direction..and there is e.m.f generated around the origin..

then what is the current density at the origin at that time? is it not just $$q\mathbf{u}$$?

5. Jan 14, 2010


text:
## On a system of operator equations.(English)Zbl 0211.17701

### MSC:

 47A62 Equations involving linear operators, with operator unknowns 46B45 Banach sequence spaces 46C15 Characterizations of Hilbert spaces 47A50 Equations and inequalities involving linear operators, with vector unknowns
Full Text:

### References:

 [1] Kurzweil, J.: On solutions of nonautonomous linear delayed differential equations which are defined and exponentially bounded for t $$\to$$-\infty. C\check{}asopis. pe\check{}st. Mat. 96, 229-238 (1971) · Zbl 0218.34065 [2] Abraham, R.; Marsden, J.: Foundations of mechanics. (1967) [3] Cohn, J.H.E.: Hadamard matrices and some generalizations. Amer. math. Monthly 72, 515-518 (1965) · Zbl 0134.25202 [4] Hall; Jr., M.: Combinatorial theory. (1967) · Zbl 0196.02401 [5] Barba, G.: Intorno al teorema di Hadamard sui determinanti a valore massimo. Giorn. mat. Battaglini 71, 70-86 (1933) · Zbl 0007.39102 [6] Wojtas, M.: On Hadamard’s inequality for the determinants of order non-divisible by 4. Colloq. math. 12, 73-83 (1964) · Zbl 0126.02604 [7] Clements, G.F.; Lindstro\"{}m, B.: A sequence of ({$$\pm$$}1) determinants with large values. Proc. amer. Math. soc. 16, 548-550 (1965) · Zbl 0138.01101 [8] J. Kurzweil, On the maximum value of a class of determinants,Mat.C\check{}asopis Sloven. Akad. Vied, to appear. [9] J. Kurzweil, Multiplicative nonnegative functionals on the set of linear maps ofm-dimensional normed linear spaces,Czechoslovak Math. J., to appear. [10] Kurzweil, J.: Solutions of linear nonautonomous functional differential equations which are exponentially bounded for t $$\to$$-\infty. J. differential equations 11, 376-384 (1972) · Zbl 0211.17702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
### Intercepting Tokens: The Empire Strikes Back in the Clone Wars

Özgür Dagdelen and Marc Fischlin

##### Abstract

We discuss interception attacks on cryptographic protocols which rely on trustworthy hardware like one-time memory tokens (Goldwasser et al., Crypto 2008). In such attacks the adversary can mount man-in-the-middle attacks and access, or even substitute, transmitted tokens. We show that many of the existing token-based protocols are vulnerable against this kind of attack, which typically lies outside of the previously considered security models. We also give a positive result for protocols remaining secure against such attacks. We present a very efficient protocol for password-based authenticated key exchange based on the weak model of one-time memory tokens. Our protocol only requires four moves, very basic operations, and the sender to send l tokens in the first step for passwords of length l. At the same time we achieve information-theoretic security in Canetti's universal composition framework (FOCS 2001) against adaptive adversaries (assuming reliable erasure), even if the tokens are not guaranteed to be transferred securely, i.e., even if the adversary can read or substitute transmitted tokens.

Note: Sept. 2013: new results and different focus

Available format(s)
Publication info
Preprint. MINOR revision.In Submission
Keywords
security modelpassword based key exchangeinformation-theoreticone-time memory tokens
Contact author(s)
oezguer dagdelen @ cased de
History
2013-09-17: last of 2 revisions
See all versions
Short URL
https://ia.cr/2012/537

CC BY

BibTeX

@misc{cryptoeprint:2012/537,
author = {Özgür Dagdelen and Marc Fischlin},
title = {Intercepting Tokens: The Empire Strikes Back in the Clone Wars},
howpublished = {Cryptology ePrint Archive, Paper 2012/537},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/537}},
url = {https://eprint.iacr.org/2012/537}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.